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

DOI10.1007/3-540-62950-5_75zbMath1379.68199OpenAlexW1605324791MaRDI QIDQ4594232

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

Mathematics Subject Classification ID

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

Related Items

First-order theory of rewriting for linear variable-separated rewrite systems: automation, formalization, certification, Grid structures and undecidable constraint theories, The Existential Fragment of the One-Step Parallel Rewriting Theory, 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, Solvability of context equations with two context variables is decidable, Thue trees, On rewrite constraints and context unification