Apr. 27 2009 2:00PM

Apr. 27 2009 3:30PM

The problem of Horn Minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function f, find a CNF representation of f which consists of a minimum possible number of clauses. This is a classical combina-torial optimization problem with many practical applications. For instance, the problem of knowledge compression for speeding up queries to propositional Horn expert systems is equivalent to HM.
HM is a computationally diffcult problem: it is known to be NP-hard even if the input is restricted to cubic Horn CNFs. On the other hand, there are two subclasses of Horn CNFs for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn CNFs. In this talk we introduce a new class of Horn CNFs which properly contains both of the known classes and describe a polynomial time HM algorithm for this new class.

Pravidelný seminář Inteligentní systémy (Kontaktní osoba: Tomáš Kroupa)