|
|
A238109
|
|
List of prefix-normal words over the alphabet {1,2}.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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 prefix normal words and prefix normal forms, arXiv:1611.09017 [cs.DM], 2016; Theoretical Computer Science, Volume 659, 10 January 2017, Pages 1-13.
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, 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.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|