Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata

Abstract

An alternating auxiliary pushdown hierarchy is defined by extending the machine model of the Logarithmic Alternation Hierarchy by a pushdown store while keeping a polynomial time bound. Although recently it was proven by Borodin et al. that the class of languages accepted by nondeterministic logarithmic space bounded auxiUary pushdown automata with a polynomial time bound is closed under complement [1], it is shown that, surprisingly, the further levels ofthis alternating auxiliary pushdown hierarchy coincide level by level with the Polynomial Hierarchy. Furthermore, PSP ACE can be characterized by simultaneously hgarithmic space and polynomial time bounded auxiliary pushdown automata with unbounded alternation. Finally, it is shown that both results generalize to arbitrary space bounds. Résumé. -Nous définissons une hiérarchie pour les machines alternantes à pile en étendant le modèle de la hiérarchie logarithmique alternante par une pile auxiliaire, tout en gardant une borne en temps polynomial. Bien qu'il a été démontré récemment par Borodin et al. que la classe des langages acceptée par un automate à pile non déterministe en espace logarithmique et en temps polynomial est fermé par complémentation, nous montrons que les niveaux supérieurs de cette hiérarchie des machines alternantes à pile auxiliaire coïncident niveau à niveau avec la hiérarchie polynomiale -un résultat assez surprenant. De plus nous montrons que PSP ACE est caractérisé par des automates bornés en espace logarithmique et en temps polynomial, en permettant une alternation non bornée. Finalement nous montrons que les deux résultats généralisent aux espaces non bornés.