Solving trace equations using lexicographical normal forms

DOI10.1007/3-540-63165-8_190zbMath1401.68161OpenAlexW1534859586MaRDI QIDQ4571965

Volker Diekert, Anca Muscholl, Yu. V. Matiyasevich

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63165-8_190

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05)

Related Items (3)

Solving trace equations using lexicographical normal forms ⋮ Solving word equations modulo partial commutations ⋮ Recognizing string graphs in NP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on the representation of trace monoids
• The parallel complexity of two problems on concurrency
• On some equations in free partially commutative monoids
• Solving trace equations using lexicographical normal forms
• Characterizations of the decidability of some problems for regular trace languages
• Inhomogeneous sorting
• Makanin's algorithm for word equations-two improvements and a generalization

This page was built for publication: Solving trace equations using lexicographical normal forms