File(s) under embargo

Reason: Publisher requirement.

10

month(s)

10

day(s)

until file(s) become available

The Billaud Conjecture for |Σ| = 4, and beyond

conference contribution
posted on 30.05.2022, 15:27 by Szymon LopaciukSzymon Lopaciuk, Daniel Reidenbach

The Billaud Conjecture, first stated in 1993, is a fundamental problem on finite words and their heirs, i.e., the words obtained by a projection deleting a single letter. The conjecture states that every morphically primitive word, i.e., a word which is not a fixed point of any non-identity morphism, has at least one morphically primitive heir. In this paper we give the proof of the Conjecture for alphabet size 4, and discuss the potential for generalising our reasoning to larger alphabets. We briefly discuss how other language-theoretic tools relate to the Conjecture, and their suitability for potential generalisations.

History

School

  • Science

Department

  • Computer Science

Published in

Developments in Language Theory

Pages

213 - 225

Source

26th International Conference on Developments in Language Theory (DLT 2022)

Publisher

Springer Nature

Version

AM (Accepted Manuscript)

Rights holder

© Springer Nature Switzerland AG

Publisher statement

This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-031-05578-2_17.

Acceptance date

28/02/2022

Publication date

2022-05-06

Copyright date

2022

ISBN

9783031055775; 9783031055782

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes in Computer Science; volume 13257

Language

en

Editor(s)

Volker Diekert; Mikhail Volkov

Location

Tampa, FL, USA

Event dates

9th May 2022 - 13th May 2022

Depositor

Mr Szymon Lopaciuk. Deposit date: 27 May 2022

Usage metrics

Read the paper on the publisher website

Categories

Exports