2019/05/28 by Fleischmann, Pamela, Kulczynski, Mitja, Nowotka, Dirk · 1 citation
#Combinatorics (math.CO) #F.4 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1905.11847
Prefix normal words are binary words in which each prefix has at least the same number of \sos as any factor of the same length. Firstly introduced by Fici and Lipták in 2011, the problem of determining the index of the prefix 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.