Computing LOGCFL certificates

DOI10.1016/S0304-3975(01)00108-6MaRDI QIDQ5958329zbMATH OpenDBLPWikidataFDO

Authors Georg Gottlob, N. Leone, Francesco Scarcello

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00108-6

zbMATH Keywords

complexityconstraint satisfactionLOGCFLparallel computationtree decompositiontreewidth

Mathematics Subject Classification ID

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

Recommendations

• Bounded Tree-Width and LOGCFL
• Properties that characterize LOGCFL
• Parallel algorithms with optimal speedup for bounded treewidth
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• The complexity of acyclic conjunctive queries

Cites work

• Alternation
• Bounded Tree-Width and LOGCFL
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Depth reduction for noncommutative arithmetic circuits
• scientific article; zbMATH DE number 3571498 (Why is no real title available?)
• scientific article; zbMATH DE number 3637281 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1304331 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• Local consistency in parallel constraint satisfaction networks
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Properties that characterize LOGCFL
• Relativized logspace and generalized quantifiers over finite ordered structures
• The complexity of acyclic conjunctive queries
• The Hardest Context-Free Language
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tree-size bounded alternation
• Two Applications of Inductive Counting for Complementation Problems

Cited in

(13)

• Properties that characterize LOGCFL
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Deterministically isolating a perfect matching in bipartite planar graphs
• Descriptive complexity of deterministic polylogarithmic time and space
• Bounded Tree-Width and LOGCFL
• Uniform Constraint Satisfaction Problems and Database Theory
• Fast parallel hypertree decompositions in logarithmic recursion depth
• Hypertree decompositions and tractable queries
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• On the complexity of constrained Nash equilibria in graphical games
• Weighted hypertree decompositions and optimal query plans
• On the power of structural decompositions of graph-based representations of constraint problems

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)