Loughborough University
Browse
Lopaciuk_Reidenbach_WORDS21_On_Billaud_Words.pdf (159.68 kB)

On Billaud words and their companions

Download (159.68 kB)
conference contribution
posted on 2021-06-29, 11:15 authored by Szymon 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)

Publisher

Springer International Publishing

Version

  • AM (Accepted Manuscript)

Rights holder

© Springer Nature

Publisher statement

The final authenticated version is available online at https://doi.org/10.1007/978-3-030-85088-3

Acceptance date

2021-06-18

Publication date

2021-09-06

Copyright date

2021

ISBN

9783030850876; 9783030850883

ISSN

1611-3349

Book series

Theoretical Computer Science and General Issues; 12847; Lecture Notes in Computer Science; 12847

Language

  • en

Editor(s)

Thierry Lecroq; Svetlana Puzynina

Location

Rouen, France (Online)

Event dates

13th September 2021 - 17th September 2021

Depositor

Dr Daniel Reidenbach. Deposit date: 29 June 2021

Usage metrics

    Loughborough Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC