The Descriptive Complexity Approach to LOGCFL

✍ Scribed by Clemens Lautemann; Pierre McKenzie; Thomas Schwentick; Heribert Vollmer

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 235 KB
• Volume: 62
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2000.1742

✦ Synopsis

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 in first-order logic with linear order. Our work extends the elaborate theory relating monoidal quantifiers to NC 1 and its subclasses. In the absence of arithmetical predicates for plus and times (equivalently, 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 reductions without arithmetic. We then prove that FO with unary groupoidal quantifiers is strictly more expressive with predicates for plus and times than without. Considering a particular groupoidal quantifier, we prove that first-order logic with the ``majority of pairs'' quantifier is strictly more expressive than first-order with majority of individuals. As a technical tool of independent interest, we define