On infinite prefix normal words
Theoretical computer science, 2021•Elsevier
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. 1
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. 1
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.1
Elsevier
