About the Lossless Reduction of the Minimal Generator Family of a Context

Minimal generators (

MG

s),

aka

minimal keys, play an important role in many theoretical and practical problem settings involving closure systems that originate in graph theory, relational database design, data mining, etc. As minima of the equivalence classes associated to closures,

MG

s underlie many compressed representations: For instance, they form premises in

canonical

implication/association rules – with closures as conclusions – that losslessly represent the entire rule family of a closure system. However,

MG

s often show an intra-class combinatorial redundancy that makes an exhaustive storage and use impractical. In this respect, the

succinct system of minimal generators

(

SSMG

) recently introduced by Dong

et al.

is a first step towards a lossless reduction of this redundancy. However, as shown elsewhere, some of the claims about

SSMG

,

e.g.

, its invariant size and lossless nature, do not hold. As a remedy, we propose here a new succinct family which restores the losslessness by adding few further elements to the

SSMG

core, while theoretically grounding the whole. Computing means for the new family are presented together with the empirical evidences about its relative size

w.r.t.

the entire

MG

family and similar structures from the literature.