RAIRO - Theoretical Informatics and Applications

Research Article

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

Bernd Borcherta1, Dietrich Kuskea2 and Frank Stephana1

a1 Universität Heidelberg, Im Neuenheimer Feld 294, 69120 Heidelberg, Germany

a2 Institut für Algebra, Technische Universität Dresden, 01062 Dresden, Germany

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.

(Received June 1998)

(Accepted January 1999)

(Online publication August 15 2002)

Key Words:

  • Leaf languages;
  • NP;
  • first-order definable languages.

Mathematics Subject Classification:

  • 03D05;
  • 68Q15;
  • 68Q68
Metrics