The sequence of open and closed prefixes of a Sturmian word

Gabriele Fici, Alessandro De Luca, Luca Q. Zamboni

Risultato della ricerca: Articlepeer review

2 Citazioni (Scopus)

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 originaleEnglish
pagine (da-a)27-45
Numero di pagine19
RivistaAdvances in Applied Mathematics
Volume90
Stato di pubblicazionePublished - 2017

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint Entra nei temi di ricerca di 'The sequence of open and closed prefixes of a Sturmian word'. Insieme formano una fingerprint unica.

Cita questo