scientific article; zbMATH DE number 1114346

MaRDI QIDQ4376064zbMATH OpenFDO

Authors Yu. Matiyasevich

Publication date 22 September 1998

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)

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:

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