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

DOI10.1016/0020-0190(94)00208-GMaRDI QIDQ673984zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• The word matching problem is undecidable for finite special string-rewriting systems that are confluent
• Some properties of finite special string-rewriting systems
• scientific article; zbMATH DE number 177883

Cites work

• scientific article; zbMATH DE number 4155934 (Why is no real title available?)
• scientific article; zbMATH DE number 1114342 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• Decidable sentences of Church-Rosser congruences
• EQUATIONS IN A FREE GROUP
• Homogeneous Thue systems and the Church-Rosser property
• Makanin's algorithm for word equations-two improvements and a generalization
• Minimal and complete word unification
• New estimates of odd exponents of infinite Burnside groups.
• On two problems related to cancellativity
• Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
• Some results on equational unification
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Word unification and transformation of generalized equations

Cited in

(4)

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

This page was built for publication: Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general

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