Premium
Some Hierarchies of Primitive Recursive Functions on Term Algebras
Author(s) -
Sprenger KlausHilmar
Publication year - 1997
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19970430208
Subject(s) - mathematics , primitive recursive function , term (time) , recursion (computer science) , hierarchy , combinatorics , natural number , algebra over a field , discrete mathematics , pure mathematics , physics , algorithm , quantum mechanics , economics , market economy
Abstract We compare two different Grzegorczyk hierarchies { H n σ } n ≥0 and { L n σ } n ≥1 on term algebras, which grow according to the height and length of terms, respectively. The solution of almost all inclusion problems among the Grzegorczyk classes and the (simultaneous) recursion number classes R n σ and S n σ on term algebras shows { H n σ } n ≥0 to generalize Weihrauch's Grzegorczyk hierarchy on words { E n k } n ≥0 to arbitrary term algebras. However, by regarding terms as words, { L n σ } n ≥1 turns out to be computationally equivalent to Weihrauch's hierarchy { E n σ } n ≥0 on the whole. Especially, L 2 σ } is equivalent to polynomial time computability and contains several natural term algebra functions. This establishes a notion of feasible term algebra functions and predicates.