Hypergraph Horn functions

DOI10.1137/23M1569162MaRDI QIDQ6499011zbMATH OpenFDO

Authors Kristóf Bérczi, Endre Boros, Kazuhisa Makino

Publication date 8 May 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1569162

zbMATH Keywords

algorithmsdualityhypergraphsHorn functions

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Hypergraphs (05C65) Boolean functions (06E30)

Recommendations

• Matroid Horn functions
• Unique key Horn functions
• Directed hypergraphs and Horn minimization
• Horn functions and their DNFs
• Horn functions and submodular Boolean functions

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3823168 (Why is no real title available?)
• scientific article; zbMATH DE number 192840 (Why is no real title available?)
• scientific article; zbMATH DE number 3365295 (Why is no real title available?)
• scientific article; zbMATH DE number 3415409 (Why is no real title available?)
• scientific article; zbMATH DE number 3018834 (Why is no real title available?)
• A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory
• An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic
• Complexity of identification and dualization of positive Boolean functions
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Horn clauses and database dependencies
• On sentences which are true of direct unions of algebras
• On the Abstract Properties of Linear Dependence
• Reasoning with models
• The Complexity of Enumeration and Reliability Problems
• The decision problem for some classes of sentences without quantifiers
• Unification as a complexity measure for logic programming
• Why Horn formulas matter in computer science: initial structures and generic examples

Cited in

(3)

• On CNF formulas irredundant with respect to unit clause propagation
• Matroid Horn functions
• Computing the D-base and D-relation in finite closure systems

This page was built for publication: Hypergraph Horn functions

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