Deciding whether a finite set of words has rank at most two (Q1210296)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Deciding whether a finite set of words has rank at most two |
scientific article |
Statements
Deciding whether a finite set of words has rank at most two (English)
0 references
24 May 1993
0 references
Let \(X\subseteq A^*\) be a finite set of words over the alphabet \(A\). The rank \(r(X)\) of \(X\) is the smallest size of a set \(Y\subseteq A^*\) of words such that \(X\subseteq Y^*\). The author presents an algorithm to check the condition \(r(X)\leq 2\). This algorithm works in \(O(n\log^ 2 m)\) time, where \(n\) is the sum of the lengths of words in \(X\) and \(m\) is the length of the longest word in \(X\).
0 references
free semigroup
0 references
complexity
0 references
rank
0 references