2014 | OriginalPaper | Buchkapitel
An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting
verfasst von : Daniel de Carvalho, Jakob Grue Simonsen
Erschienen in: Rewriting and Typed Lambda Calculi
Verlag: Springer International Publishing
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
We define the class of
constrained cons-free
rewriting systems and show that this class characterizes
P
, the set of languages decidable in polynomial time on a deterministic Turing machine. The main novelty of the characterization is that it allows very liberal properties of term rewriting, in particular non-deterministic evaluation: no reduction strategy is enforced, and systems are allowed to be non-confluent.