An applicative recursion scheme for FPH

Reinhard Kahle

(Lisboa)

Ben-Amram, Loff, and Oitavem introduced a characterization of the functions in the polynomial hierarchy using a monotonicity condition. Based on this characterization, we introduce an applicative theory whose provably total functions are exactly the functions computable in the polynomial hierarchy of time.

(Joint work with Isabel Oitavem.)
Thursday 31st March 2011, 14:45
Far-134 (Video Conferencing Room)
Department of Computer Science