Properties that characterize LOGCFL
From MaRDI portal
Recommendations
Cites work
- 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?)
- A New Pebble Game that Characterizes Parallel Complexity Classes
- A complexity theory based on Boolean algebra
- A taxonomy of problems with fast parallel algorithms
- Alternating Pushdown and Stack Automata
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- 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
(37)- Complexity theory for splicing systems
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- From bidirectionality to alternation.
- Cost register automata for nested words
- Properties of probabilistic pushdown automata
- Computing LOGCFL certificates
- Properties of probabilistic pushdown automata
- String shuffle: circuits and graphs
- Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones
- Arithmetic circuits: the chasm at depth four gets wider
- The complexity of graph languages generated by hyperedge replacement
- Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract)
- The parameterized space complexity of model-checking bounded variable first-order logic
- Monomials in arithmetic circuits: complete problems in the counting hierarchy
- Derandomizing isolation in space-bounded settings
- The complexity of computing maximal word functions
- The descriptive complexity approach to LOGCFL
- Generalized quantifier and a bounded arithmetic theory for LOGCFL
- Tradeoff lower lounds for stack machines
- Properties that characterize LOGCFL
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Extensions to Barrington's M-program model
- The complexity of short two-person games
- DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
- The dynamic complexity of acyclic hypergraph homomorphisms
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Characterizing Valiant's algebraic complexity classes
- Unambiguity of circuits
- Depth lower bounds for monotone semi-unbounded fan-in circuits.
- On growing context-sensitive languages
- Empty alternation
- String distances and intrusion detection: Bridging the gap between formal languages and computer security
- Dual VP classes
- Subclasses of \textsc{Ptime} interpreted by programming languages
- Two dynamic programming algorithms for which interpreted pebbling helps
- Data independence of read, write, and control structures in PRAM computations
- Parallelizing time with polynomial circuits
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)
