Computing LOGCFL certificates
From MaRDI portal
Publication:5958329
DOI10.1016/S0304-3975(01)00108-6zbMath0992.68062WikidataQ59259713 ScholiaQ59259713MaRDI QIDQ5958329
Francesco Scarcello, Georg Gottlob, Nicola Leone
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
On the complexity of constrained Nash equilibria in graphical games ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Weighted hypertree decompositions and optimal query plans ⋮ Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width. ⋮ Deterministically isolating a perfect matching in bipartite planar graphs ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Hypertree decompositions and tractable queries ⋮ On the power of structural decompositions of graph-based representations of constraint problems ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Uniform Constraint Satisfaction Problems and Database Theory
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree-size bounded alternation
- Properties that characterize LOGCFL
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Local consistency in parallel constraint satisfaction networks
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The complexity of acyclic conjunctive queries
- Two Applications of Inductive Counting for Complementation Problems
- Alternation
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Bounded Tree-Width and LOGCFL
- Relativized logspace and generalized quantifiers over finite ordered structures
- The Hardest Context-Free Language
- Depth reduction for noncommutative arithmetic circuits
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
