Prefix normal words are binary words that have no factor with more 1s than the prefix of the same length. Finite prefix normal words were introduced in [Fici and Lipták, DLT 2011]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order.
On Infinite Prefix Normal Words
Cicalese, Ferdinando
;Lipták, Zsuzsanna
;ROSSI, MASSIMILIANO
2019-01-01
Abstract
Prefix normal words are binary words that have no factor with more 1s than the prefix of the same length. Finite prefix normal words were introduced in [Fici and Lipták, DLT 2011]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
Cicalese2019_Chapter_OnInfinitePrefixNormalWords.pdf
solo utenti autorizzati
Tipologia:
Versione dell'editore
Licenza:
Copyright dell'editore
Dimensione
656.43 kB
Formato
Adobe PDF
|
656.43 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.