Overlap-free words and finite automata (Q1261466)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Overlap-free words and finite automata |
scientific article |
Statements
Overlap-free words and finite automata (English)
0 references
16 September 1993
0 references
Overlap-free words on a two letters alphabet are shown to be represented by a rational language over a 25 letters alphabet. The construction extends the results of \textit{A. Restivo} and \textit{S. Salemi} [Bull. EATCS 21, 49-56 (1983)]. This rather surprising rationality result allows several applications: a linear-time algorithm to test the overlap-free property; density of the set of overlap-free words; prolongability of these words, among others.
0 references
overlap-free words
0 references
finite automata
0 references
combinatorics
0 references
