Julien Leroy - An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2

dmtcs:1249 - Discrete Mathematics & Theoretical Computer Science, May 4, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1249
An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2Article

Authors: Julien Leroy 1

  • 1 Mathematics Research Unit

An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n + 1) − p(n) ≤ 2 S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is S-adic with Card(S) ≤ 3 27. In this paper, we improve this result by giving an S-adic characterization of these subshifts with a set S of 5 morphisms, solving by this way the S-adic conjecture for this particular case.

https://doi.org/10.46298/dmtcs.1249
Source: HAL:hal-01179422v1
Volume: Vol. 16 no. 1
Section: Automata, Logic and Semantics
Published on: May 4, 2014
Accepted on: July 23, 2015
Submitted on: June 3, 2013
Keywords: special factor,factor complexity,S-adic conjecture,Rauzy graph,S-adic subshift,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Licence: Attribution 4.0 International (CC BY 4.0)

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 418 times.
This article's PDF has been downloaded 389 times.