The Existential Fragment of the One-Step Parallel Rewriting Theory

DOI10.1007/978-3-642-02348-4_6MaRDI QIDQ3636820zbMATH OpenOpenAlexFDO

Authors Aleksy Schubert

Publication date 30 June 2009

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

Full work available at URL https://doi.org/10.1007/978-3-642-02348-4_6

Mathematics Subject Classification ID

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

Recommendations

• The first-order theory of one-step rewriting is undecidable
• The first-order theory of linear one-step rewriting is undecidable
• A new result about the decidability of the existential one-step rewriting theory
• Undecidability of the first order theory of one-step right ground rewriting
• The undecidability of the first-order theories of one step rewriting in linear canonical systems

Cites work

• A new result about the decidability of the existential one-step rewriting theory
• Deciding the satisfiability of quantifier free formulae on one-step rewriting
• Grid structures and undecidable constraint theories
• scientific article; zbMATH DE number 4043232 (Why is no real title available?)
• Learning to win process-control games watching game-masters
• On rewrite constraints and context unification
• On the undecidability of second-order unification
• Rewriting logic: Roadmap and bibliography
• The first-order theory of linear one-step rewriting is undecidable
• The first-order theory of one step rewriting in linear noetherian systems is undecidable
• Toward the concurrent implementation of computational systems
• Undecidability of the first order theory of one-step right ground rewriting

Cited in

(4)

• 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
• Deciding the satisfiability of quantifier free formulae on one-step rewriting
• A new result about the decidability of the existential one-step rewriting theory

This page was built for publication: The Existential Fragment of the One-Step Parallel Rewriting Theory

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