It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>>

A theory, in this context, is a Boolean formula; it is used to classify instances, or truth assignments. Theories can model real-world phenomena, and can do so more or less correctly. The theory revision, or concept revision, problem is to correct a given, roughly correct concept. This problem is considered ... more >>>

Given a Boolean matrix and a threshold t, a subset of the columns is frequent if there are at least t rows having a 1 entry in each corresponding position. This concept is used in the algorithmic, combinatorial approach to knowledge discovery and data mining. We consider the complexity aspects ... more >>>