On existentially first-order definable languages and their relation to NP. (English) Zbl 0917.68076
Larsen, Kim G. (ed.) et al., Automata, languages and programming. 25th international colloquium, ICALP ’98. Aalborg, Denmark, July 13–17, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1443, 17-28 (1998).
Summary: Under the assumption that the polynomial-time hierarchy does not collapse we show that a regular language \(L\) determines NP as an unbalanced polynomial-time leaf language if and only if \(L\) is existentially but not quantifier-free definable in \(\text{FO}[<,\min, \max,-1,+1]\). The proof relies on the result of J.-E. Pin and P. Weil [Theory Comput. Syst. 30, No. 4, 383-422 (1997; Zbl 0872.68119)] characterizing the automata of existentially first-order definable languages.
For the entire collection see [Zbl 0893.00039].
For the entire collection see [Zbl 0893.00039].
MSC:
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q45 | Formal languages and automata |
