Some decision problems for traces (Q4376064)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1114346
Language Label Description Also known as
default for all languages
No label defined
    English
    Some decision problems for traces
    scientific article; zbMATH DE number 1114346

      Statements

      22 September 1998
      0 references
      independence alphabets
      0 references
      congruences
      0 references
      trace equations
      0 references
      decidability
      0 references
      monoids
      0 references
      0 references
      Some decision problems for traces (English)
      0 references
      An independence alphabet is a pair \(\langle A;I\rangle\) where \(A\) is a finite set and \(I\) is an irreflexive symmetric binary relation on \(A\) (modeling the relation: two members of \(A\) commute). The relation \(I\) induces a congruence on the monoid \(A^*\). Classes of this congruence are called traces in \(\langle A;I\rangle\). The author studies several decidability questions involving traces. A system of trace equations can be viewed as \(T=\langle A,X,S,C,I\rangle\) where \(\langle A;I\rangle\) is an independence alphabet, \(X\) is a finite set of unknowns disjoint from \(A\), \(S\) is a set of string equations in \(A\cup X\), and \(C\) is a set of commutativity equations in \(A\cup X\). A solution of \(T\) is any assignment of values to members of \(X\) which gives an \(I\)-stable solution to each equation in \(S\) and a solution to every equation from \(C\). The author proves the existence of an algorithm that tells for any given system of trace equations whether it has a solution. For the entire collection see [Zbl 0865.00035].
      0 references

      Identifiers