Lattice of Maximal Antichains
Vijay K. Garg · 2015
This chapter discusses the lattice of maximal antichains with applications to global predicate detection. It shows that some global predicates can be detected on the lattice of maximal antichains instead of consistent cuts, thereby providing an exponential reduction in the complexity of detecting them. The chapter also discusses algorithms for computing LMA for a finite poset P with implicit representation. It defines three different but isomorphic lattices: the lattice of maximal antichain ideals, the lattice of maximal antichains, and the lattice of strict ideals. The incremental algorithm for lattice of maximal antichains (ILMA) algorithm is a modification of the algorithm given by Nourine and Raynaud based on computing the lattice of strict ideals. The algorithm, due to Ganter and Reuter, is general enough to enumerate any lattice that is a subset of the Boolean lattice (or a product space) and is defined using a closure operator.