Lopaciuk_Reidenbach_WORDS21_On_Billaud_Words.pdf (159.68 kB)
On Billaud words and their companions
conference contribution
posted on 2021-06-29, 11:15 authored by Szymon Lopaciuk, Daniel ReidenbachThe 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, ProceedingsPages
129-141Source
13th International Conference on Combinatorics on Words (WORDS 2021)Publisher
Springer International PublishingVersion
- AM (Accepted Manuscript)
Rights holder
© Springer NaturePublisher statement
The final authenticated version is available online at https://doi.org/10.1007/978-3-030-85088-3Acceptance date
2021-06-18Publication date
2021-09-06Copyright date
2021ISBN
9783030850876; 9783030850883ISSN
1611-3349Publisher version
Book series
Theoretical Computer Science and General Issues; 12847; Lecture Notes in Computer Science; 12847Language
- en
Editor(s)
Thierry Lecroq; Svetlana PuzyninaLocation
Rouen, France (Online)Event dates
13th September 2021 - 17th September 2021Depositor
Dr Daniel Reidenbach. Deposit date: 29 June 2021Usage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC