Achieving new upper bounds for the hypergraph duality problem through logic

DOI10.1145/2603088.2603103MaRDI QIDQ4635628zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Enrico Malizia

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10871/33327

zbMATH Keywords

\(\mathrm{TC}^0\)algorithmscomplexityDNF dualityfirst-order logicfirst-order logic with counting quantifiersgraph theoryhypergraph dualityhypergraph transversalshypergraphslimited nondeterminismlogical analysis of algorithms

Mathematics Subject Classification ID

Logic in computer science (03B70) Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Achieving new upper bounds for the hypergraph duality problem through logic
• scientific article; zbMATH DE number 517080
• scientific article; zbMATH DE number 179052
• scientific article; zbMATH DE number 5762364
• The Logic of Graph-Theoretic Duality
• Satisfiability on hypergraphs
• scientific article; zbMATH DE number 120352
• New upper bounds for the problem of maximal satisfiability
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• Hybrid logics and NP graph properties

Cited in

(8)

• Understanding the complexity of axiom pinpointing in lightweight description logics
• Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs
• Inconsistency-tolerant query answering for existential rules
• Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting
• A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
• Achieving new upper bounds for the hypergraph duality problem through logic
• On a logical approach to estimating computational complexity of potentially intractable problems.
• Explanations for query answers under existential rules

This page was built for publication: Achieving new upper bounds for the hypergraph duality problem through logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635628)