On the rank of the subsets of a free monoid (Q1193899): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Jean Néraud / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Tero J.Harju / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4430300 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sur le théorème du defaut / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the defect theorem and simplifiability / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5673640 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Elementariness of a finite set of words is co-NP-complete / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the deficit of a finite set of words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4140407 / rank | |||
Normal rank |
Latest revision as of 14:26, 16 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the rank of the subsets of a free monoid |
scientific article |
Statements
On the rank of the subsets of a free monoid (English)
0 references
27 September 1992
0 references
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)\).
0 references
word monoid
0 references
rank
0 references
defect theorem
0 references
free monoid
0 references
catenation
0 references
iteration
0 references