The word matching problem is undecidable for finite special string-rewriting systems that are confluent

DOI10.1007/3-540-63165-8_218zbMath1401.68138OpenAlexW1549267059MaRDI QIDQ4571993

Paliath Narendran, Friedrich Otto

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_218

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Related Items (2)

A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN GROUPS ⋮ Equational unification, word unification, and 2nd-order equational unification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general
• Word unification and transformation of generalized equations
• EQUATIONS IN A FREE GROUP
• Minimal and complete word unification
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Makanin's algorithm for word equations-two improvements and a generalization

This page was built for publication: The word matching problem is undecidable for finite special string-rewriting systems that are confluent