Properties that characterize LOGCFL
From MaRDI portal
Publication:1176109
DOI10.1016/0022-0000(91)90020-6zbMath0776.68046OpenAlexW2051700974MaRDI QIDQ1176109
Publication date: 25 June 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(91)90020-6
LOGCFLlanguages log space reducible to context-free languagesparallel complexity classpolynomial proof-sizesemi- unbounded fan-in circuit familiessemi-unboundedness
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unnamed Item, Dual VP classes, Generalized quantifier and a bounded arithmetic theory for LOGCFL, The dynamic complexity of acyclic hypergraph homomorphisms, Empty alternation, Subclasses of \textsc{Ptime} interpreted by programming languages, From bidirectionality to alternation., Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract), Parallelizing time with polynomial circuits, Arithmetic circuits: the chasm at depth four gets wider, Isolation, matching, and counting uniform and nonuniform upper bounds, The complexity of short two-person games, Properties that characterize LOGCFL, Complexity theory for splicing systems, Data independence of read, write, and control structures in PRAM computations, Characterizing Valiant's algebraic complexity classes, Extensions to Barrington's M-program model, Unambiguity of circuits, Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}, Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits, The descriptive complexity approach to LOGCFL, String shuffle: circuits and graphs, Properties of probabilistic pushdown automata, Two dynamic programming algorithms for which interpreted pebbling helps, The complexity of graph languages generated by hyperedge replacement, Computing LOGCFL certificates, On growing context-sensitive languages, DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS, Tradeoff lower lounds for stack machines, Cost Register Automata for Nested Words, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Properties of probabilistic pushdown automata, Derandomizing Isolation in Space-Bounded Settings, Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones, String distances and intrusion detection: Bridging the gap between formal languages and computer security, Monomials in arithmetic circuits: complete problems in the counting hierarchy, The complexity of computing maximal word functions
Cites Work
- Membership for growing context-sensitive grammars is polynomial
- Tree-size bounded alternation
- On uniform circuit complexity
- Upper and lower bounds for first order expressibility
- Properties that characterize LOGCFL
- Simulation of Parallel Random Access Machines by Circuits
- Alternating Pushdown and Stack Automata
- A taxonomy of problems with fast parallel algorithms
- The Complexity of Languages Generated by Attribute Grammars
- A complexity theory based on Boolean algebra
- Two Applications of Inductive Counting for Complementation Problems
- A New Pebble Game that Characterizes Parallel Complexity Classes
- Alternation
- On Relating Time and Space to Size and Depth
- On the Tape Complexity of Deterministic Context-Free Languages
- The complexity of the membership problem for some extensions of context-free languagest†
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
