Properties that characterize LOGCFL
From MaRDI portal
Recommendations
Cites work
- A complexity theory based on Boolean algebra
- A New Pebble Game that Characterizes Parallel Complexity Classes
- A taxonomy of problems with fast parallel algorithms
- Alternating Pushdown and Stack Automata
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- scientific article; zbMATH DE number 3960999 (Why is no real title available?)
- scientific article; zbMATH DE number 4090800 (Why is no real title available?)
- scientific article; zbMATH DE number 3555903 (Why is no real title available?)
- scientific article; zbMATH DE number 3571498 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- Membership for growing context-sensitive grammars is polynomial
- On Relating Time and Space to Size and Depth
- On the Tape Complexity of Deterministic Context-Free Languages
- On uniform circuit complexity
- Properties that characterize LOGCFL
- Simulation of Parallel Random Access Machines by Circuits
- The Complexity of Languages Generated by Attribute Grammars
- The complexity of the membership problem for some extensions of context-free languagest†
- Tree-size bounded alternation
- Two Applications of Inductive Counting for Complementation Problems
- Upper and lower bounds for first order expressibility
Cited in
(41)- The complexity of short two-person games
- Properties that characterize LOGCFL
- Extensions to Barrington's M-program model
- Unambiguity of circuits
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Properties of probabilistic pushdown automata
- Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones
- The complexity of computing maximal word functions
- From bidirectionality to alternation.
- Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Data independence of read, write, and control structures in PRAM computations
- String shuffle: circuits and graphs
- Two dynamic programming algorithms for which interpreted pebbling helps
- The complexity of graph languages generated by hyperedge replacement
- Monomials in arithmetic circuits: complete problems in the counting hierarchy
- Dual VP classes
- Parallelizing time with polynomial circuits
- Complexity theory for splicing systems
- Characterizing Valiant's algebraic complexity classes
- The dynamic complexity of acyclic hypergraph homomorphisms
- Depth lower bounds for monotone semi-unbounded fan-in circuits.
- Cost register automata for nested words
- String distances and intrusion detection: Bridging the gap between formal languages and computer security
- scientific article; zbMATH DE number 1304331 (Why is no real title available?)
- Arithmetic circuits: the chasm at depth four gets wider
- The parameterized space complexity of model-checking bounded variable first-order logic
- Properties of probabilistic pushdown automata
- Empty alternation
- On growing context-sensitive languages
- Derandomizing isolation in space-bounded settings
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- The descriptive complexity approach to LOGCFL
- Computing LOGCFL certificates
- Subclasses of \textsc{Ptime} interpreted by programming languages
- Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract)
- Alternation-bounded semi-unbounded fan-in cascading circuits and the complementation closure property
- On the complexity of problems on tree-structured graphs
- Tradeoff lower lounds for stack machines
- Generalized quantifier and a bounded arithmetic theory for LOGCFL
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
This page was built for publication: Properties that characterize LOGCFL
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1176109)
