A238109 List of prefix-normal words over the alphabet {1,2}.

1, 2, 11, 12, 22, 111, 112, 121, 122, 222, 1111, 1112, 1121, 1122, 1212, 1221, 1222, 2222, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12121, 12122, 12212, 12221, 12222, 22222, 111111, 111112, 111121, 111122, 111211, 111212, 111221, 111222, 112112

Offset: 1

Author

N. J. A. Sloane, Mar 02 2014

Keywords

• nonn

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

• Rémy Sigrist, Table of n, a(n) for n = 1..16906 (terms up to length 16)
• 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

Cf. A194850.

Extensions

More terms from Rémy Sigrist, Feb 12 2017