Loughborough University
Browse

On Billaud words and their companions

Download (672.88 kB)
journal contribution
posted on 2022-12-13, 15:34 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, and we use it to rephrase and study the Billaud Conjecture in more detail.

History

School

  • Science

Department

  • Computer Science

Published in

Theoretical Computer Science

Volume

940

Issue

Part A

Pages

231-253

Publisher

Elsevier BV

Version

  • VoR (Version of Record)

Rights holder

© The Authors

Publisher statement

This is an Open Access Article. It is published by Elsevier under the Creative Commons Attribution 4.0 International Licence (CC BY). Full details of this licence are available at: https://creativecommons.org/licenses/by/4.0/

Acceptance date

2022-11-06

Publication date

2022-11-09

Copyright date

2022

ISSN

0304-3975

Language

  • en

Depositor

Szymon Lopaciuk. Deposit date: 15 November 2022

Usage metrics

    Loughborough Publications

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC