On the rank of the subsets of a free monoid

Jean Néraud
LIFAR, Université de Rouen, Place Émile Blondel, 76821 Mont-Saint-Aignan, France

Abstract: Given an arbitrray subset of the free monoid A*, we define its rank by the integer :
r(X)=min { |Y| : X in Y*}
We establish some properties of the rank in connection with operations on the sets of words. More precisely , given two subsets X,Y of A*, the following properties hold :

(a) If X is a subset of Y, then we have r(X)≤r(Y)
(b) r(X inter Y) ≤ min {r(X), r(Y)}
(c) max{ r(X), r(Y)} ≤ r(X U Y) ≤ r(X)+r(Y)
(d) max{ r(X), r(Y)}-1 ≤ r(XY) ≤ r(X)+r(Y)
Moreover, the equality r(XY) ≤ r(X)+r(Y) holds for sets of arbitrary tall cardinality.
r(X*)=r(X)
(e) r(YoX) ≤ min {r(X), r(Y)}

Page d'accueil de l'atelier
Présentation de l'atelier
Description des activités
Bibliographie