Some decision problems for traces

DOI10.1007/3-540-63045-7_25MaRDI QIDQ4376064zbMATH OpenFDO

Authors Yu. Matiyasevich

Publication date 22 September 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63045-7_25

zbMATH Keywords

congruencesdecidabilityindependence alphabetsmonoidstrace equations

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Free semigroups, generators and relations, word problems (20M05)

Review text

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].

Recommendations

• Characterizations of the decidability of some problems for regular trace languages
• Solving trace equations using lexicographical normal forms
• Solving word equations modulo partial commutations
• Alphabetical satisfiability problem for trace equations
• The homomorphism problem for trace monoids.

Cited in

(10)

• The star problem and the finite power property in trace monoids: Reductions beyond C4
• Solving word equations modulo partial commutations
• Word equations in non-deterministic linear space
• Parabolic and quasiparabolic subgroups of free partially commutative groups.
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• On systems of equations over free partially commutative groups.
• Finding all solutions of equations in free groups and monoids with involution
• Solving trace equations using lexicographical normal forms
• On some decision problems for trace codings
• Quadratic equations in graph products of groups and the exponent of periodicity

This page was built for publication: Some decision problems for traces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376064)