Search
 
loader loading subjects...
cover
New Results for Horn Cores and Envelopes of Horn Disjunctions
Thomas Eiter, Kazuhisa Makino
60 - 64
10.3233/978-1-58603-891-5-60
Frontiers in Artificial Intelligence and Applications
Volume 178: ECAI 2008
Abstract

We provide a characterization of Horn cores for formulas in conjunctive normal form (CNF) and, based on it, a novel algorithm for computing Horn cores of disjunctions of Horn CNFs that has appealing properties (e.g., it is polynomial for a bounded disjunction). Furthermore, we show that recognizing the Horn envelope of a disjunction of two Horn CNFs is intractable, and that computing a compact Horn CNF for it (that is irredundant and prime) is not feasible in polynomial total time unless P=NP; this answers an open problem.

Download
Creative Commons License