Advertisement
Published in:
2012 | OriginalPaper | Chapter
A New Order-Theoretic Characterisation of the Polytime Computable Functions
Authors : Martin Avanzini, Naohi Eguchi, Georg Moser
Published in: Programming Languages and Systems
Publisher: Springer Berlin Heidelberg
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 propose a new order-theoretic characterisation of the class of polytime computable functions. To this avail we define the
small polynomial path order
(
sPOP
*
for short). This termination order entails a new syntactic method to analyse the innermost runtime complexity of term rewrite systems fully automatically: for any rewrite system compatible with sPOP
*
that employs recursion upto depth
d
, the (innermost) runtime complexity is polynomially bounded of degree
d
. This bound is tight.