On Collapsing Prefix Normal Words

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

*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications : 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Proceedings
EditorsAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
Number of pages13
Publication date2020
ISBN (Print)978-3-030-40607-3
ISBN (Electronic)978-3-030-40608-0
Publication statusPublished - 2020
Event14th International Conference on Language and Automata Theory and Applications - Milano, Italy
Duration: 4 Mar 20206 Mar 2020
Conference number: 14


Conference14th International Conference on Language and Automata Theory and Applications
SeriesLecture Notes in Computer Science (LNCS)


Dive into the research topics of 'On Collapsing Prefix Normal Words'. Together they form a unique fingerprint.

Cite this