On the rank of the subsets of a free monoid (Q1193899): Difference between revisions

For a subset \(X \subseteq A^*\) of a word monoid \(A^*\), the rank of \(X\) is defined to be the minimal cardinality \(r(X)\) of a set \(Y\) such that \(X \subset Y^*\). By the defect theorem \(r(X) < | X|\) if \(X^*\) is not a free monoid. The author studies how the rank function behaves with respect to the operations of union, intersection, catenation and iteration. In particular, for catenation it is shown that \(\max\{r(X),r(Y)\}-1\leq r(XY) \leq r(X) + r(Y)\).