Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general

DOI10.1016/0020-0190(94)00208-GzbMath0875.68593OpenAlexW2023356641WikidataQ127720512 ScholiaQ127720512MaRDI QIDQ673984

Friedrich Otto

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00208-g

zbMATH Keywords

Formal languagesString-rewritingWord equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Some independence results for equational unification ⋮ The word matching problem is undecidable for finite special string-rewriting systems that are confluent ⋮ Equational unification, word unification, and 2nd-order equational unification ⋮ The word problem for one-relation monoids: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New estimates of odd exponents of infinite Burnside groups.
• Decidable sentences of Church-Rosser congruences
• Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
• Homogeneous Thue systems and the Church-Rosser property
• On two problems related to cancellativity
• Word unification and transformation of generalized equations
• EQUATIONS IN A FREE GROUP
• Minimal and complete word unification
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Makanin's algorithm for word equations-two improvements and a generalization