期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：automata and formal languages, Computational Complexity, descriptive complexity, finite model theory
