Undecidability of the first order theory of one-step right ground rewriting

DOI10.1007/3-540-62950-5_75zbMATH Open1379.68199OpenAlexW1605324791MaRDI QIDQ4594232FDOQ4594232

Jerzy Marcinkowski

Publication date: 17 November 2017

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

Full work available at URL: https://doi.org/10.1007/3-540-62950-5_75

Recommendations

• The first-order theory of one-step rewriting is undecidable
• The first-order theory of linear one-step rewriting is undecidable
• The undecidability of the first-order theories of one step rewriting in linear canonical systems
• Decidable first-order theories of one-step rewriting in trace monoids
• scientific article; zbMATH DE number 2086668

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Decidability of theories and sets of sentences (03B25)

Cited In (12)

• The undecidability of the first-order theories of one step rewriting in linear canonical systems
• First-order theory of rewriting for linear variable-separated rewrite systems: automation, formalization, certification
• A new method for undecidability proofs of first order theories
• The Existential Fragment of the One-Step Parallel Rewriting Theory
• The first-order theory of linear one-step rewriting is undecidable
• Solvability of context equations with two context variables is decidable
• 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
• The first-order theory of one-step rewriting is undecidable

This page was built for publication: Undecidability of the first order theory of one-step right ground rewriting

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