On the deficit of a finite set of words (Q1822632): Difference between revisions
From MaRDI portal
Latest revision as of 10:27, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the deficit of a finite set of words |
scientific article |
Statements
On the deficit of a finite set of words (English)
0 references
1990
0 references
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\).
0 references
rank
0 references
deficit
0 references
minimal dependent set
0 references
maximal independent sets
0 references