Double Horn functions

DOI10.1006/inco.1998.2713zbMath0912.06011OpenAlexW1965189594MaRDI QIDQ1271644

Kazuhisa Makino, Thomas Eiter, Toshihide Ibaraki

Publication date: 16 May 1999

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2713

zbMATH Keywords

disjunctive normal formscomputational propertiespartially defined Boolean functionsdouble Horn functionspolynomnial-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Boolean functions (06E30)

Related Items (7)

Union-closed sets and Horn Boolean functions ⋮ Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions ⋮ Bidual Horn functions and extensions ⋮ Computational aspects of monotone dualization: a brief survey ⋮ On the difference of Horn theories ⋮ Decision lists and related Boolean functions ⋮ Recognition and dualization of disguised bidual Horn functions.

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial characterization of read-once formulae
• Why Horn formulas matter in computer science: initial structures and generic examples
• Occam's razor
• On generating all maximal independent sets
• Functions computed by monotone Boolean formulas with no repeated variables
• Horn functions and their DNFs
• Structure identification in relational data
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Horn logic, search and satisfiability. A collection of papers in memory of Robert G. Jeroslow
• Error-free and best-fit extensions of partially defined Boolean functions
• Horn functions and submodular Boolean functions
• Horn approximations of empirical data
• Generating Boolean \(\mu\)-expressions
• A Way to Simplify Truth Functions
• The Complexity of Very Simple Boolean Formulas with Applications
• A theory of the learnable
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Computational limitations on learning from examples
• Preferential Arrangements
• On sentences which are true of direct unions of algebras
• The decision problem for some classes of sentences without quantifiers

This page was built for publication: Double Horn functions