Maximal Closed Set and Half-Space Separations in Finite Closure Systems
  Several concept learning problems can be regarded as special cases of
half-space separation in abstract closure systems over finite ground sets. For
the typical scenario that the closure system is implicitly given via a closure
operator, we show that the half-space separation problem is NP-complete. As a
first approach to overcome this negative result, we relax the problem to
maximal closed set separation, give a generic greedy algorithm solving this
problem with a linear number of closure operator calls, and show that this
bound is sharp. For a second direction, we consider Kakutani closure systems
and prove that they are algorithmically characterized by the greedy algorithm.
As a first special case of the general problem setting, we consider Kakutani
closure systems over graphs and give a sufficient condition for this kind of
closure systems in terms of forbidden graph minors. For a second special case,
we then focus on closure systems over finite lattices, give an improved
adaptation of the generic greedy algorithm, and present an application
concerning subsumption lattices.
