2014 | OriginalPaper | Chapter
An Implicit Characterization of the Polynomial-Time Decidable Sets by Cons-Free Rewriting
Authors : Daniel de Carvalho, Jakob Grue Simonsen
Published in: Rewriting and Typed Lambda Calculi
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.