Double Horn functions

DOI10.1006/INCO.1998.2713MaRDI QIDQ1271644zbMATH OpenOpenAlexFDO

Authors Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino

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

computational propertiesdisjunctive normal formsdouble Horn functionspartially defined Boolean functionspolynomnial-time algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1136094
• Bidual Horn functions and extensions
• scientific article; zbMATH DE number 1104330
• Horn Extensions of a Partially Defined Boolean Function

Cites work

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

Cited in

(11)

• Recognition and dualization of disguised bidual Horn functions.
• Bidual Horn functions and extensions
• Horn Extensions of a Partially Defined Boolean Function
• scientific article; zbMATH DE number 1104330 (Why is no real title available?)
• scientific article; zbMATH DE number 1136094 (Why is no real title available?)
• About some properties of Horn and anti-Horn functions
• On the difference of Horn theories
• Decision lists and related Boolean functions
• Union-closed sets and Horn Boolean functions
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• Computational aspects of monotone dualization: a brief survey

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Double Horn functions

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