Prefix normal words are binary words with the property that no factor has more 1s than the prefix of the same length. Finite prefix normal words were introduced in Fici and Lipták (2011) [18]. 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
;
2021-01-01

Abstract

Prefix normal words are binary words with the property that no factor has more 1s than the prefix of the same length. Finite prefix normal words were introduced in Fici and Lipták (2011) [18]. 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.
2021
Combinatorics on words Prefix normal words, Infinite words, Sturmian words, Abelian complexity, Paperfolding word, Thue-Morse sequence, Lexicographic order
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397521000268-main.pdf

solo utenti autorizzati

Licenza: Copyright dell'editore
Dimensione 760.81 kB
Formato Adobe PDF
760.81 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.

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