The first-order theory of one-step rewriting is undecidable

DOI10.1007/3-540-61464-8_59zbMath1503.68162OpenAlexW60855923MaRDI QIDQ5055866

Ralf Treinen

Publication date: 9 December 2022

Published in: Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61464-8_59

Mathematics Subject Classification ID

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

Related Items

Decreasing diagrams with two labels are complete for confluence of countable systems, Grid structures and undecidable constraint theories, The first-order theory of linear one-step rewriting is undecidable, On equality up-to constraints over finite trees, context unification, and one-step rewriting, The undecidability of the first-order theories of one step rewriting in linear canonical systems, Thue trees, Iterated relabeling tree transducers, On rewrite constraints and context unification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new method for undecidability proofs of first order theories
• Rewriting techniques and applications. 5th international conference RTA-93, Montréal, Canada, June 16--18, 1993. Proceedings
• Semantic confluence tests and completion methods
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Encompassment properties and automata with constraints
• More problems in rewriting
• Problems in rewriting III
• A variant of a recursively unsolvable problem