arnold beckmann's pages

A term rewriting characterization of the polytime functions and related complexity classes

File: PDF-File

Author: Arnold Beckmann and Andreas Weiermann
Title: A term rewriting characterization of the polytime functions and related complexity classes
Journal: Arch. Math. Logic 1996, 36: 11-30
DOI: 10.1007/s001530050054

Abstract: A natural term rewriting framework for the Bellantoni Cook schemata of predicative recursion, which yields a canonical definition of the polynomial time computable functions, is introduced. In terms of an exponential function both, an upper bound and a lower bound are proved for the resulting derivation lengths of the functions in question. It is proved that any natural reduction strategy yields an algorithm which runs in exponential time. We give an example in which this estimate is tight. It is proved that the resulting derivation lengths become polynomially bounded in the lengths of the inputs if the rewrite rules are only applied to terms in which the safe arguments -- no restrictions are assumed for the normal arguments -- consist of values, i.e. numerals, and not of names, i.e. non numeral terms. It is proved that in the latter situation any inside first reduction strategy and any head reduction strategy yield algorithms, for the function under consideration, for which the running time is bounded by an appropriate polynomial in the lengths of the input. A feasible rewrite system for predicative recursion with predicative parameter substitution is defined. It is proved that the derivation lengths of this rewrite system are polynomially bounded in the lengths of the inputs. As a corollary we reobtain BellantoniĀ“s result stating that predicative recursion is closed under predicative parameter recursion.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!