Abstract
A finite word is closed if it contains a factor that occurs both as a prefix and as a suffix but does not have internal occurrences, otherwise it is open. We are interested in the oc-sequence of a word, which is the binary sequence whose n-th element is 0 if the prefix of length n of the word is open, or 1 if it is closed. We exhibit results showing that this sequence is deeply related to the combinatorial and periodic structure of a word. In the case of Sturmian words, we show that these are uniquely determined (up to renaming letters) by their oc-sequence. Moreover, we prove that the class of finite Sturmian words is a maximal element with this property in the class of binary factorial languages. We then discuss several aspects of Sturmian words that can be expressed through this sequence. Finally, we provide a linear-time algorithm that computes the oc-sequence of a finite word, and a linear-time algorithm that reconstructs a finite Sturmian word from its oc-sequence
Lingua originale | English |
---|---|
pagine (da-a) | 27-45 |
Numero di pagine | 19 |
Rivista | Advances in Applied Mathematics |
Volume | 90 |
Stato di pubblicazione | Published - 2017 |
All Science Journal Classification (ASJC) codes
- ???subjectarea.asjc.2600.2604???