Lecture Notes in Computer Science, 2008, Volume 5028/2008, 42-51, DOI: 10.1007/978-3-540-69407-6_5

Pure Iteration and Periodicity
A Note on Some Small Sub-recursive Classes

Mathias Barra

View Related Documents

Abstract

We define a hierarchy of small sub-recursive classes, based on the schema of pure iteration. is compared with a similar hierarchy, based on primitive recursion, for which a collapse is equivalent to a collapse of the small Grzegorczyk-classes. Our hierarchy does collapse, and the induced relational class is shown to have a highly periodic structure; indeed a unary predicate is decidable in iff it is definable in Presburger Arithmetic. The concluding discussion contrasts our findings to those of Kutyłowski [12].

Fulltext Preview

Image of the first page of the fulltext document