For any infinite word r over a, b we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (great- est, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as; bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately peri- odic word of a particular form. This result is based on a lemma concerning sequences of infinite words.

Morse and Hedlund's skew Sturmian words revisited

Pirillo G
2008

Abstract

For any infinite word r over a, b we associate two infinite words min(r), max(r) such that any prefix of min(r) (max(r), respectively) is the lexicographically smallest (great- est, respectively) among the factors of r of the same length. We prove that (min(r); max(r)) = (as; bs) for some infinite word s if and only if r is a proper Sturmian word or an ultimately peri- odic word of a particular form. This result is based on a lemma concerning sequences of infinite words.
2008
Istituto di Analisi dei Sistemi ed Informatica ''Antonio Ruberti'' - IASI
words
lexicographic order
Sturmian words
episturmian words
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/455067
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 4
social impact