On collapsing prefix normal words

DOI10.1007/978-3-030-40608-0_29MaRDI QIDQ782603zbMATH OpenOpenAlexFDO

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

Publication date 27 July 2020

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

zbMATH Keywords

palindromesbinary wordsprefix normal wordscollapsing wordsextension-critical words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

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

Cited in

(7)

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

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)