2010/03/31 by Steven Widmer, Widmer, Steven · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1003.6123
openalex publication_date 2010/03/31 · arxiv created 2010/04/05 · arxiv updated 2010/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a countable set X (usually taken to be the natural numbers or the integers), an infinite permutation πof X is a linear ordering of X. This paper investigates the combinatorial complexity of the infinite permutation on the natural numbers associated with the well-known and well-studied Thue-Morse word. A formula for the complexity is established by studying patterns in subpermutations and the action of the Thue-Morse morphism on the subpermutations.