The descriptive complexity approach to LOGCFL

DOI10.1006/JCSS.2000.1742MaRDI QIDQ5946058zbMATH OpenOpenAlexFDO

Authors Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer

Publication date 14 October 2001

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2000.1742

zbMATH Keywords

aperiodic nondeterministic finite automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1304331
• Generalized quantifier and a bounded arithmetic theory for LOGCFL
• On Second-Order Monadic Groupoidal Quantifiers
• scientific article; zbMATH DE number 1841830
• Properties that characterize LOGCFL

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• \(NC^ 1\): The automata-theoretic viewpoint
• An infinite hierarchy of intersections of context-free languages
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Complexity of some problems from the theory of automata
• Elementary Properties of the Finite Ranks
• Expressibility and Parallel Complexity
• Extensions to Barrington's M-program model
• Finite degrees of ambiguity in pattern languages
• Finite monoids and the fine structure of NC ¹
• scientific article; zbMATH DE number 6003856 (Why is no real title available?)
• scientific article; zbMATH DE number 47306 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 2079028 (Why is no real title available?)
• scientific article; zbMATH DE number 1559593 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Lindström quantifiers and leaf language definability
• On finite monoids having only trivial subgroups
• On the Tape Complexity of Deterministic Context-Free Languages
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Properties that characterize LOGCFL
• Regular languages in \(NC\)
• The Hardest Context-Free Language

Cited in

(13)

• The many faces of a translation
• A language-theoretical approach to descriptive complexity
• The arithmetic complexity of tensor contraction
• A circuit complexity approach to transductions
• On Second-Order Monadic Groupoidal Quantifiers
• Extensional Uniformity for Boolean Circuits
• Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]
• scientific article; zbMATH DE number 1304331 (Why is no real title available?)
• scientific article; zbMATH DE number 2051828 (Why is no real title available?)
• Regular representations of uniform TC^0
• First-order logics: some characterizations and closure properties
• Characterizing NC^1 with typed monoids
• Generalized quantifier and a bounded arithmetic theory for LOGCFL

This page was built for publication: The descriptive complexity approach to LOGCFL

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946058)