Undecidability of ground reducibility for word rewriting systems with variables

DOI10.1016/0020-0190(94)00188-5zbMath0998.68529OpenAlexW2039995028WikidataQ58064552 ScholiaQ58064552MaRDI QIDQ674184

Gregory Kucherov, Michaël Rusinowitch

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)00188-5

zbMATH Keywords

Term rewriting systemsFormal languagesPattern matchingTheory of computation

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items

Finite degrees of ambiguity in pattern languages ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ Multi-pattern languages

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• On sufficient-completeness and related properties of term rewriting systems
• Thue systems as rewriting systems
• Sufficient-completeness, ground-reducibility and their complexity
• Semantic confluence tests and completion methods
• Inclusion is undecidable for pattern languages

This page was built for publication: Undecidability of ground reducibility for word rewriting systems with variables