On Existentially First-Order Definable Languages and Their Relation to NP

¹ Universität Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, Germany
² Institut für Algebra, Technische Universität Dresden, 01062 Dresden, Germany

Received: June 1998
Accepted: January 1999

Abstract

Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals  iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.

Résumé

Sous l'hypothèse que la hiérarchie de temps polynomial est stricte, nous montrons que, pour un langage régulier L, la classe des langages de feuille de la hiérarchie polynomiale associée à L est égale à NP si et seulement si L est définissable dans FO[<, min, max, +1, −1] par une formule existentielle comportant au moins un quantificateur. De plus, il n'existe aucune classe de ce type entre NP et co-1-NP ou NP⊕co-NP. Les preuves reposent sur un résultat de Pin et Weil qui caractérise les automates des langages définissables par des formules existentielles du premier ordre.