2012/01/12 by Martin Avanzini, Avanzini, Martin, Naohi Eguchi +3 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #D.2.4 #D.2.8 #F.2.2 #F.4.1 #F.4.2 #FOS: Computer and information sciences #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1201.2553
openalex publication_date 2012/01/12 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28
We propose a new order, the small polynomial path order (sPOP* for short).\nThe order sPOP* provides a characterisation of the class of polynomial time\ncomputable function via term rewrite systems. Any polynomial time computable\nfunction gives rise to a rewrite system that is compatible with sPOP*. On the\nother hand any function defined by a rewrite system compatible with sPOP* is\npolynomial time computable. Technically sPOP* is a tamed recursive path order\nwith product status. Its distinctive feature is the precise control provided.\nFor any rewrite system that is compatible with sPOP* that makes use of\nrecursion up to depth d, the (innermost) runtime complexity is bounded from\nabove by a polynomial of degree d.\n