On collapsing prefix normal words

DOI10.1007/978-3-030-40608-0_29zbMATH Open1460.68080arXiv1905.11847OpenAlexW3013522911MaRDI QIDQ782603FDOQ782603

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

Publication date: 27 July 2020

Abstract: Prefix normal words are binary words in which each prefix has at least the same number of $so$s as any factor of the same length. Firstly introduced by Fici and Lipt'ak 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.

Full work available at URL: https://arxiv.org/abs/1905.11847

Recommendations

• On prefix normal words
• On infinite prefix normal words
• On prefix normal words and prefix normal forms
• On infinite prefix normal words
• Weighted prefix normal words: mind the gap

zbMATH Keywords

palindromesbinary wordsprefix normal wordscollapsing wordsextension-critical words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cited In (7)

• Weighted prefix normal words: mind the gap
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• On prefix normal words and prefix normal forms
• On infinite prefix normal words
• On infinite prefix normal words
• On prefix normal words
• COLLAPSING WORDS: A PROGRESS REPORT

This page was built for publication: On collapsing prefix normal words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782603)