Logical Approaches to Computational Barriers

Pure iteration and periodicity

Speaker:
| Mathias Barra |

Slot: |
Array, 17:30-17:50, col. 5 |

We define a hierarchy IT of small sub-recursive classes, based on the schema of pure iteration. IT 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 IT iff it is definable in Presburger Arithmetic.

websites: Arnold Beckmann | 2008-05-18 |