Computing LOGCFL certificates
From MaRDI portal
Publication:5958329
DOI10.1016/S0304-3975(01)00108-6zbMATH Open0992.68062DBLPjournals/tcs/GottlobLS02WikidataQ59259713 ScholiaQ59259713MaRDI QIDQ5958329
Francesco Scarcello, Georg Gottlob, N. Leone
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Alternation
- The complexity of acyclic conjunctive queries
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Bounded Tree-Width and LOGCFL
- The Hardest Context-Free Language
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Properties that characterize LOGCFL
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- Tree-size bounded alternation
- Two Applications of Inductive Counting for Complementation Problems
- Relativized logspace and generalized quantifiers over finite ordered structures
- Depth reduction for noncommutative arithmetic circuits
- Local consistency in parallel constraint satisfaction networks
Cited In (11)
- On the complexity of constrained Nash equilibria in graphical games
- Uniform Constraint Satisfaction Problems and Database Theory
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Hypertree decompositions and tractable queries
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Weighted hypertree decompositions and optimal query plans
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- On the power of structural decompositions of graph-based representations of constraint problems
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Descriptive complexity of deterministic polylogarithmic time and space
This page was built for publication: Computing LOGCFL certificates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958329)
