ECCC-Report TR98-059https://eccc.weizmann.ac.il/report/1998/059Comments and Revisions published for TR98-059en-usWed, 07 Oct 1998 04:59:28 +0200
Paper TR98-059
| The Descriptive Complexity Approach to LOGCFL |
C. Lautemann,
Pierre McKenzie,
T. Schwentick,
H. Vollmer
https://eccc.weizmann.ac.il/report/1998/059
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
transducers.
Wed, 07 Oct 1998 04:59:28 +0200https://eccc.weizmann.ac.il/report/1998/059