Solving word equations modulo partial commutations

DOI10.1016/S0304-3975(98)00313-2zbMath0930.68074WikidataQ56896629 ScholiaQ56896629MaRDI QIDQ1960424

Anca Muscholl, Yu. V. Matiyasevich, Volker Diekert

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

tracesword equationspartial commutationsword equations with regular constraints

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Finding all solutions of equations in free groups and monoids with involution ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Parabolic and quasiparabolic subgroups of free partially commutative groups. ⋮ On systems of equations over free partially commutative groups ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logical definability on infinite traces
• The parallel complexity of two problems on concurrency
• On some equations in free partially commutative monoids
• On equations in free semigroups and groups
• Combinatorial problems of commutation and rearrangements
• Definability in the Existential Theory of Concatenation and Undecidable Extensions of this Theory
• The expressibility of languages and relations by word equations
• Solving trace equations using lexicographical normal forms
• Characterizations of the decidability of some problems for regular trace languages
• Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
• Inhomogeneous sorting
• Makanin's algorithm for word equations-two improvements and a generalization