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.

Abstract:

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.