Properties that characterize LOGCFL

DOI10.1016/0022-0000(91)90020-6zbMath0776.68046OpenAlexW2051700974MaRDI QIDQ1176109

H. Venkateswaran

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

zbMATH Keywords

LOGCFLlanguages log space reducible to context-free languagesparallel complexity classpolynomial proof-sizesemi- unbounded fan-in circuit familiessemi-unboundedness

Mathematics Subject Classification ID

Related Items (37)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Properties that characterize LOGCFL