Horn Extensions of a Partially Defined Boolean Function
Authors:
- Kazuhisa MakinoKMKazuhisa Makino
- Ken-Ichi HatanakaKHKen-Ichi Hatanaka
- Toshihide IbarakiTIToshihide Ibaraki
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (6) , 2168-2186
Abstract
Given a partially defined Boolean function (pdBf) (T,F), we investigate in thispaper how to find a Horn extension $f: \{0,1\}^n \mapsto \{0,1\}$, which is consistent with (T,F), where $T \subseteq \{0,1\}^n$ denotes a set of true Boolean vectors (or positive examples) and $F \subseteq \{0,1\}^n$ denotes a set of false Boolean vectors (or negative examples). Given a pdBf (T,F), it is known that the existence of a Horn extension can be checked in polynomial time. As there are many Horn extensions, however, we consider those extensions f which have maximal and minimal sets T(f) of the true vectors of f, respectively. For a pdBf (T,F), there always exists the unique maximal (i.e., maximum) Horn extension, but there are in general many minimal Horn extensions. We first show that a polynomial time membership oracle can be constructed for the maximum extension, even if its disjunctive normal form (DNF) can be very long. Our main contribution is to show that checking if a given Horn DNF represents a minimal extension and generating a Horn DNF of a minimal Horn extension can both be done in polynomial time. We also can check in polynomial time if a pdBf (T,F) has the unique minimal Horn extension. However, the problems of finding a Horn extension f with the smallest |T(f)| and of obtaining a Horn DNF, whose number of literals is smallest, are both NP-hard.
Keywords
This publication has 23 references indexed in Scilit:
- On the Complexity of Dualization of Monotone Disjunctive Normal FormsJournal of Algorithms, 1996
- Decomposability of partially defined Boolean functionsDiscrete Applied Mathematics, 1995
- Horn approximations of empirical dataArtificial Intelligence, 1995
- A linear time algorithm for unique Horn satisfiabilityInformation Processing Letters, 1993
- Optimal compression of propositional Horn knowledge bases: complexity and approximationArtificial Intelligence, 1993
- Structure identification in relational dataArtificial Intelligence, 1992
- On generating all maximal independent setsInformation Processing Letters, 1988
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- A Way to Simplify Truth FunctionsThe American Mathematical Monthly, 1955
- The decision problem for some classes of sentences without quantifiersThe Journal of Symbolic Logic, 1943