Unique key Horn functions
From MaRDI portal
Publication:2672584
DOI10.1016/j.tcs.2022.04.022zbMath1500.68005arXiv2002.06964OpenAlexW3006494912MaRDI QIDQ2672584
Kazuhisa Makino, Petr Kučera, Ondřej Čepek, Endre Boros, Kristóf Bérczi
Publication date: 13 June 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.06964
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Hypergraphs (05C65) Classical propositional logic (03B05) Boolean functions (06E30) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Construction and learnability of canonical Horn formulas
- Hydras: complexity on general graphs and a subclass of trees
- Hydras: directed hypergraphs and Horn formulas
- Dualization of regular Boolean functions
- An O(m n) algorithm for regular set-covering problems
- Candidate keys for relations
- Optimal compression of propositional Horn knowledge bases: Complexity and approximation
- A note on hyperplane generation
- On enumerating all minimal solutions of feedback problems
- Polynomial-time inference of all valid implications for Horn and related formulae
- The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On computing all abductive explanations from a propositional Horn theory
- On the Approximability of Influence in Social Networks
- Canonical Horn Representations and Query Learning
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Minimal Representation of Directed Hypergraphs
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- The Maximum Latency and Identification of Positive Boolean Functions
- On Approximating Target Set Selection
- On incomparable collections of sets
- On the Complexity of Computing Generators of Closed Sets
- Algorithms – ESA 2004
- Approximating Minimum Representations of Key Horn Functions
