Linear time and the power of one first-order universal quantifier
The aim of this paper is to give two new logical characterizations of NLIN (nondeterministic linear time) improving significantly a previous characterization of E. Grandjean (1994, SIAM J. Comput. 23, 573-597: and F. Olive, 1998, Comput. Complexity 7, 54-97). It is known that NLIN coincides with the class of problems definable by formulas of the prenex form There Existsf(1)... There Existsf(k) phi where the f(i) are unary function symbols and phi is first-order. prenex, with only one universal quantifier. We show that the characterization remains true in the two following cases: (a) Unary functions are replaced by a single binary relation whose outdegree is bounded by some fixed constant h. (b) When only ordered structures are considered. unary functions are restricted to be bijective. (C) 2002 Elsevier Science (USA).
linear time descriptive complexity finite model theory