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

DOI10.1016/0020-0190(94)00208-GzbMATH Open0875.68593OpenAlexW2023356641WikidataQ127720512 ScholiaQ127720512MaRDI QIDQ673984FDOQ673984

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

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

zbMATH Keywords

Formal languagesString-rewritingWord equations

Mathematics Subject Classification ID

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

Cites Work

• New estimates of odd exponents of infinite Burnside groups.
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Decidable sentences of Church-Rosser congruences
• Title not available (Why is that?)
• On two problems related to cancellativity
• Word unification and transformation of generalized equations
• EQUATIONS IN A FREE GROUP
• Some results on equational unification
• Solutions principales et rang d'un système d'équations avec constantes dans le monoide libre
• Homogeneous Thue systems and the Church-Rosser property

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)