Achieving new upper bounds for the hypergraph duality problem through logic

DOI10.1145/2603088.2603103zbMath1395.68151OpenAlexW2088113003WikidataQ59259467 ScholiaQ59259467MaRDI QIDQ4635628

Enrico Malizia, Georg Gottlob

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

complexityalgorithmsfirst-order logicgraph theoryhypergraphslimited nondeterminismhypergraph transversals\(\mathrm{TC}^0\)DNF dualityfirst-order logic with counting quantifiershypergraph dualitylogical analysis of algorithms

Mathematics Subject Classification ID

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

Related Items (6)

Inconsistency-tolerant query answering for existential rules ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ Understanding the complexity of axiom pinpointing in lightweight description logics ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting

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