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

DOI10.1007/3-540-61464-8_59MaRDI QIDQ5055866zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The first-order theory of linear one-step rewriting is undecidable
• Undecidability of the first order theory of one-step right ground rewriting
• The first-order theory of one step rewriting in linear noetherian systems is undecidable
• The undecidability of the first-order theories of one step rewriting in linear canonical systems
• scientific article; zbMATH DE number 4060699
• Decidable first-order theories of one-step rewriting in trace monoids
• Publication:4938601
• First-order Frege theory is undecidable
• scientific article; zbMATH DE number 4210102
• A new method for undecidability proofs of first order theories

Cites work

• scientific article; zbMATH DE number 48095 (Why is no real title available?)
• scientific article; zbMATH DE number 48157 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• A new method for undecidability proofs of first order theories
• A variant of a recursively unsolvable problem
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Encompassment properties and automata with constraints
• More problems in rewriting
• Problems in rewriting III
• Rewriting techniques and applications. 5th international conference RTA-93, Montréal, Canada, June 16--18, 1993. Proceedings
• Semantic confluence tests and completion methods

Cited in

(16)

• The undecidability of the first-order theories of one step rewriting in linear canonical systems
• A new method for undecidability proofs of first order theories
• The Existential Fragment of the One-Step Parallel Rewriting Theory
• Iterated relabeling tree transducers
• The first-order theory of linear one-step rewriting is undecidable
• Decreasing diagrams with two labels are complete for confluence of countable systems
• On rewrite constraints and context unification
• Grid structures and undecidable constraint theories
• Decidable first-order theories of one-step rewriting in trace monoids
• On equality up-to constraints over finite trees, context unification, and one-step rewriting
• Thue trees
• scientific article; zbMATH DE number 1405621 (Why is no real title available?)
• scientific article; zbMATH DE number 1405622 (Why is no real title available?)
• Undecidability of the first order theory of one-step right ground rewriting
• scientific article; zbMATH DE number 2086668 (Why is no real title available?)
• Analysis of rewriting-based systems as first-order theories

This page was built for publication: The first-order theory of one-step rewriting is undecidable

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