Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Primitive Rewriting
verfasst von : Nachum Dershowitz
Erschienen in: Processes, Terms and Cycles: Steps on the Road to Infinity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Undecidability results in rewriting have usually been proved by reduction from undecidable problems of Turing machines or, more recently, from Post’s Correspondence Problem. Another natural candidate for proofs regarding term rewriting is Recursion Theory, a direction we promote in this contribution.
We present some undecidability results for “primitive” term rewriting systems, which encode primitive-recursive definitions, in the manner suggested by Klop. We also reprove some undecidability results for orthogonal and non-orthogonal rewriting by applying standard results in recursion theory.