On Collapsing Prefix Normal Words

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

*Kontaktforfatter

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

Abstrakt

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.
OriginalsprogEngelsk
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
ForlagSpringer
Publikationsdato2020
Sider412-424
ISBN (Trykt)978-3-030-40607-3
ISBN (Elektronisk)978-3-030-40608-0
DOI
StatusUdgivet - 2020
NavnLecture Notes in Computer Science (LNCS)
Vol/bind12038
ISSN0302-9743

    Fingerprint

Citationsformater

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