Skip to Main content Skip to Navigation
Journal articles

On sets of indefinitely desubstitutable words

Gwenaël Richomme 1, 2
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The stable set associated to a given set S of nonerasing endomorphisms or substitutions is the set of all right infinite words that can be indefinitely desubstituted over S. This notion generalizes the notion of sets of fixed points of morphisms. It is linked to S-adicity and to property preserving morphisms. Two main questions are considered. Which known sets of infinite words are stable sets? Which ones are stable sets of a finite set of substitutions? While bringing answers to the previous questions, some new characterizations of several well-known sets of words such as the set of binary balanced words or the set of episturmian words are presented. A characterization of the set of nonerasing endomorphisms that preserve episturmian words is also provided.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03005771
Contributor : Gwenaël Richomme <>
Submitted on : Saturday, November 14, 2020 - 5:27:46 PM
Last modification on : Thursday, June 10, 2021 - 5:11:06 PM
Long-term archiving on: : Monday, February 15, 2021 - 6:20:33 PM

Files

words_version_longue_pour_TCS....
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-03005771, version 1
  • ARXIV : 2011.07838

Citation

Gwenaël Richomme. On sets of indefinitely desubstitutable words. Theoretical Computer Science, Elsevier, 2021, 857, pp.97-113. ⟨lirmm-03005771⟩

Share

Metrics

Record views

62

Files downloads

46