------------------------------------------------------------------------------- ******************************************************************************* ------------------------------------------------------------------------------- B O S T O N U N I V E R S I T Y Computer Science Department C O L L O Q U I U M Monday, September 30, 1996 3:00 pm (Coffee served at 2:30 pm) Seminar Room / MCS 135 ------------------------------------------------------------------------------- ******************************************************************************* ------------------------------------------------------------------------------- RECURSION AND ITERATION OVER FINITE STRUCTURES Katherine St. John Department of Mathematics University of Pennsylvania Philadelphia, PA 19104-6395 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 begin by discussing two arguments from this body of work -- the space-bound arguments of Paterson and Hewitt and Tiuryn's 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. Further, we will discuss the extensions of this work to higher order iteration and recursion. This is joint work with Assaf Kfoury. ------------------------------------------------------------------------------- For colloquium info, including directions, see http://www.cs.bu.edu/colloquium For more information contact Prof. David Yates -------------------------------------------------------------------------------