Computing LOGCFL certificates

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)

zbMATH Keywords

complexityparallel computationtreewidthtree decompositionconstraint satisfactionLOGCFL

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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