Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
From MaRDI portal
Publication:4637759
DOI10.1137/15M1027267zbMath1506.68037arXiv1407.2912WikidataQ62044178 ScholiaQ62044178MaRDI QIDQ4637759
Publication date: 26 April 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.2912
complexityalgorithmsfirst-order logicgraph theoryhypergraphslimited nondeterminismhypergraph transversalsDNF dualityfirst-order logic with counting quantifiershypergraph dualitylogical analysis of algorithms
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Logic in computer science (03B70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting ⋮ Query answering over inconsistent knowledge bases: a probabilistic approach ⋮ Preference-based inconsistency-tolerant query answering under existential rules
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Elements of finite model theory.
- A global parallel algorithm for the hypergraph transversal problem
- An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
- Computational aspects of monotone dualization: a brief survey
- On the complexity of monotone dualization and generating minimal hypergraph transversals
- A theory of diagnosis from first principles
- A correction to the algorithm in Reiter's theory of diagnosis
- On the complexity of inferring functional dependencies
- On maximal frequent and minimal infrequent sets in binary matrices
- Monotone Boolean dualization is in co-NP\([\log^{2}n\).]
- On the universal and existential fragments of the \(\mu\)-calculus
- Parametrized complexity theory.
- Complexity of identification and dualization of positive Boolean functions
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- On uniformity within \(NC^ 1\)
- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
- How to assign votes in a distributed system
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Algorithms for inferring functional dependencies from relations
- On the Amount of Nondeterminism and the Power of Verifying
- Achieving new upper bounds for the hypergraph duality problem through logic
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Computer Science Logic
- Advances in Artificial Intelligence
