Applicative theories for the polynomial hierarchy of time and its levels
In the paper under review applicative theories chracterizing the polynomial hierarchy of time (FPH) and its levels are introduced. They are based on a characterization of the functions in the polynomial hierarchy using monotonicity constraints introduced by Ben-Amram, Loff and Oitavem. Further, lower and upper bounds are considered. The proof of the lower bound follows from a straightforward embedding of the function algebra and the upper bound is carried out by an adaptation of the proofs given by Strahm.
scientific article; zbMATH DE number 6154066