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

DOI10.1007/3-540-61464-8_59zbMATH Open1503.68162OpenAlexW60855923MaRDI QIDQ5055866FDOQ5055866

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A variant of a recursively unsolvable problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Semantic confluence tests and completion methods
• Encompassment properties and automata with constraints
• 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
• Title not available (Why is that?)
• More problems in rewriting
• Problems in rewriting III

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Undecidability of the first order theory of one-step right ground rewriting
• Title not available (Why is that?)
• 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)