On the deficit of a finite set of words (Q1822632): Difference between revisions

We define the rank of a finite set X as the integer: \(r(X)=\min \{| Y|:\) \(X\subseteq Y^*\}\) and its deficit as \(def(X)=| X| - r(X)\). X is independent iff \(def(X)=0\), otherwise it is dependent. We define the notion of maximal independent set, and the dual notion of minimal dependent set. A characterization of the maximal independent sets is established, moreover we prove that given an integer n, there exists a set X, such that \(def(X)=1\), and such that for all the sets D satisfying \(def(X-D)=0\), we have \(| D| \geq n\).