OFFSET
1,2
COMMENTS
A word of length n over the alphabet {a,b} is prefix-normal if for all 1 <= k <= n, no factor of length k has more a's than the prefix of length k. For example, abbabab is not prefix-normal because aba has more a's than abb.
LINKS
P. Burcsi, G. Fici, Zs. Lipták, F. Ruskey and J. Sawada, On Combinatorial Generation of Prefix Normal Words, arXiv:1401.6346 [cs.DS], 2014; Combinatorial Pattern Matching 2014, Lecture Notes in Computer Science 8486, 60-69, 2014.
P. Burcsi, G. Fici, Zs. Lipták, F. Ruskey, and J. Sawada, On prefix normal words and prefix normal forms, arXiv:1611.09017 [cs.DM], 2016; Theoretical Computer Science, Volume 659, 10 January 2017, Pages 1-13.
Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, Bubble-Flip—A new generation algorithm for prefix normal words, arXiv:1712.05876 [cs.DS], 2017-2018; Theoretical Computer Science, Volume 743, 26 September 2018, Pages 38-52.
Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, On Infinite Prefix Normal Words, arXiv:1811.06273 [math.CO], 2018.
G. Fici and Zs. Lipták, On Prefix Normal Words, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238, 2011.
Pamela Fleischmann, On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words, Ph.D. Dissertation, Kiel University (Germany, 2021).
Pamela Fleischmann, Mitja Kulczynski, and Dirk Nowotka, On Collapsing Prefix Normal Words, arXiv:1905.11847 [cs.FL], 2019.
Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, On Collapsing Prefix Normal Words, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.
Zsuzsanna Lipták, Open problems on prefix normal words, also in Dagstuhl Reports (2018) Vol. 8, Issue 7, 59-61.
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Mar 02 2014
EXTENSIONS
More terms from Rémy Sigrist, Feb 12 2017
STATUS
approved