posted on 2021-06-29, 11:15authored bySzymon Lopaciuk, Daniel Reidenbach
The Billaud Conjecture, which has been open since 1993, is a fundamental problem on finite words w and their heirs, i.e., the words obtained by deleting every occurrence of a given letter from w. It posits that every morphically primitive word, i.e. a word which is a fixed point of the identity morphism only, has at least one morphically primitive heir. In this paper, we introduce and investigate the related class of so-called Billaud words, i.e. words whose all heirs are morphically imprimitive. We provide a characterisation of morphically imprimitive Billaud words, using a new concept. We show that there are two phenomena through which words can have morphically imprimitive heirs, and we highlight that only one of those occurs in morphically primitive words. Finally, we examine our concept further, use it to rephrase the Billaud Conjecture and study its difficulty.
History
School
Science
Department
Computer Science
Published in
Combinatorics on Words. 13th International Conference, WORDS 2021, Rouen, France, September 13–17, 2021, Proceedings
Pages
129-141
Source
13th International Conference on Combinatorics on Words (WORDS 2021)