On Collapsing Prefix Normal Words

Pamela Fleischmann*, Mitja Kulczynski, Dirk Nowotka, Danny Bøgsted Poulsen


Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review


Prefix normal words are binary words in which each prefix has at least the same number of 1 s as any factor of the same length. Firstly introduced in 2011, the problem of determining the index (amount of equivalence classes for a given word length) of the prefix normal equivalence relation is still open. In this paper, we investigate two aspects of the problem, namely prefix normal palindromes and so-called collapsing words (extending the notion of critical words). We prove characterizations for both the palindromes and the collapsing words and show their connection. Based on this, we show that still open problems regarding prefix normal words can be split into certain subproblems.
TitelLanguage and Automata Theory and Applications : 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Proceedings
RedaktørerAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
Antal sider13
ISBN (Trykt)978-3-030-40607-3
ISBN (Elektronisk)978-3-030-40608-0
StatusUdgivet - 2020
NavnLecture Notes in Computer Science (LNCS)



Fleischmann, P., Kulczynski, M., Nowotka, D., & Poulsen, D. B. (2020). On Collapsing Prefix Normal Words. I A. Leporati, C. Martín-Vide, D. Shapira, & C. Zandron (red.), Language and Automata Theory and Applications: 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Proceedings (s. 412-424). Springer. Lecture Notes in Computer Science (LNCS), Bind. 12038 https://doi.org/10.1007/978-3-030-40608-0_29