Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-059 | 15th September 1998 00:00

The Descriptive Complexity Approach to LOGCFL



Building upon the known generalized-quantifier-based first-order
characterization of LOGCFL, we lay the groundwork for a deeper
investigation. Specifically, we examine subclasses of LOGCFL arising
from varying the arity and nesting of groupoidal quantifiers. Our
work extends the elaborate theory relating monoidal quantifiers to
NC^1 and its subclasses. In the absence of the BIT predicate, we
resolve the main issues: we show in particular that no single
outermost unary groupoidal quantifier with FO can capture all the
context-free languages, and we obtain the surprising result that a
variant of Greibach's ``hardest context-free language'' is
LOGCFL-complete under quantifier-free BIT-free projections. We then
prove that FO with unary groupoidal quantifiers is strictly more
expressive with the BIT predicate than without. Considering a
particular groupoidal quantifier, we prove that first-order logic
with majority of pairs is strictly more expressive than first-order
with majority of individuals. As a technical tool of independent
interest, we define the notion of an aperiodic nondeterministic
finite automaton and prove that FO translations are precisely the
mappings computed by single-valued aperiodic nondeterministic finite

ISSN 1433-8092 | Imprint