Adam Borchert ; Narad Rampersad - Permutation complexity of images of Sturmian words by marked morphisms

dmtcs:4042 - Discrete Mathematics & Theoretical Computer Science, June 4, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-20
Permutation complexity of images of Sturmian words by marked morphismsArticle

Authors: Adam Borchert ; Narad Rampersad

    We show that the permutation complexity of the image of a Sturmian word by a binary marked morphism is $n+k$ for some constant $k$ and all lengths $n$ sufficiently large.

    Comment: 9 pages

    https://doi.org/10.23638/DMTCS-20-1-20
    Source: arXiv.org:1710.08820
    Volume: Vol. 20 no. 1
    Section: Combinatorics
    Published on: June 4, 2018
    Accepted on: May 21, 2018
    Submitted on: November 2, 2017
    Keywords: Mathematics - Combinatorics, Computer Science - Formal Languages and Automata Theory, 68R15
    Licence: arXiv.org - Non-exclusive license to distribute
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Share and export

    Consultation statistics

    This page has been seen 674 times.
    This article's PDF has been downloaded 408 times.