Jorge Almeida ; Ondřej Klíma - Binary patterns in the Prouhet-Thue-Morse sequence

dmtcs:5460 - Discrete Mathematics & Theoretical Computer Science, August 30, 2021, vol. 23, no. 3 - https://doi.org/10.46298/dmtcs.5460
Binary patterns in the Prouhet-Thue-Morse sequenceArticle

Authors: Jorge Almeida ORCID; Ondřej Klíma

    We show that, with the exception of the words $a^2ba^2$ and $b^2ab^2$, all (finite or infinite) binary patterns in the Prouhet-Thue-Morse sequence can actually be found in that sequence as segments (up to exchange of letters in the infinite case). This result was previously attributed to unpublished work by D. Guaiana and may also be derived from publications of A. Shur only available in Russian. We also identify the (finitely many) finite binary patterns that appear non trivially, in the sense that they are obtained by applying an endomorphism that does not map the set of all segments of the sequence into itself.


    Volume: vol. 23, no. 3
    Section: Automata, Logic and Semantics
    Published on: August 30, 2021
    Accepted on: August 2, 2021
    Submitted on: May 15, 2019
    Keywords: Mathematics - Combinatorics,Primary: 68R15, Secondary: 11B85, 20M05, 20M35, 37B10
    Funding:
      Source : OpenAIRE Graph
    • Pseudovariedades de semigrupos ordenados; Code: SFRH/BSAB/142872/2018

    Consultation statistics

    This page has been seen 724 times.
    This article's PDF has been downloaded 450 times.