  The monotone duality problem is defined as follows: Given two monotone
formulas f and g in iredundant DNF, decide whether f and g are dual. This
problem is the same as duality testing for hypergraphs, that is, checking
whether a hypergraph H consists of precisely all minimal transversals of a
simple hypergraph G. By exploiting a recent problem-decomposition method by
Boros and Makino (ICALP 2009), we show that duality testing for hypergraphs,
and thus for monotone DNFs, is feasible in DSPACE[log^2 n], i.e., in quadratic
logspace. As the monotone duality problem is equivalent to a number of problems
in the areas of databases, data mining, and knowledge discovery, the results
presented here yield new complexity results for those problems, too. For
example, it follows from our results that whenever for a Boolean-valued
relation (whose attributes represent items), a number of maximal frequent
itemsets and a number of minimal infrequent itemsets are known, then it can be
decided in quadratic logspace whether there exist additional frequent or
infrequent itemsets.
