Katherine St. John
University of Pennsylvania
Recursion on Classes of Finite Structures
- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- February 23, 2:30 p.m.
When does recursion differ from iteration? On "nice" infinite
structures (e.g. N), the functions defined by recursion are exactly
those defined by iteration. But for definitions given uniformly over
classes of finite structures, recursion can differ from iteration.
This difference was explored by many people in the context of Dynamic
Logic. We will discuss two arguments from this body of work.
We will first use the space-bound arguments of Paterson and Hewitt to
bound the closure ordinals of recursions with only two variables over
classes of finite Herbrand interpretations (e.g. finitely generated
finite structures of a fixed signature).
Tiuryn gives an elegant proof that the number of elements "seen" in
the course of an iteration of an explicit boolean-valued function, on
the complete tree of height n, is bounded by a polynomial in n. We
extend this result to finite Herbrand interpretations of any finite
functional signature with equality.