Permutation complexity and the letter doubling map

DOI10.1142/S0129054112400680MaRDI QIDQ2841975zbMATH OpenFDO

Authors Steven Widmer

Publication date 30 July 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.5527

zbMATH Keywords

infinite permutationpermutation complexitySturmian wordsThue-Morse worduniformly recurrent

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: Given a countable set X (usually taken to be N or Z), an infinite permutation $pi$ of X is a linear ordering ${<}_{p}i$ of X. This paper investigates the combinatorial complexity of infinite permutations on N associated with the image of uniformly recurrent aperiodic binary words under the letter doubling map. An upper bound for the complexity is found for general words, and a formula for the complexity is established for the Sturmian words and the Thue-Morse word.

Recommendations

• Permutation complexity related to the letter doubling map
• Permutation complexity of the Thue-Morse word
• On the infinite permutation generated by the period doubling word
• Infinite permutations of lowest maximal pattern complexity
• On periodicity and low complexity of infinite permutations

Cites work

• Enumeration of factors in the Thue-Morse word
• On periodicity and low complexity of infinite permutations
• On the infinite permutation generated by the period doubling word
• Permutation complexity of the Thue-Morse word
• Sequences with minimal block growth
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups

Cited in

(6)

• On the infinite permutation generated by the period doubling word
• Permutation complexity related to the letter doubling map
• scientific article; zbMATH DE number 4132415 (Why is no real title available?)
• Permutation complexity of images of Sturmian words by marked morphisms
• On the permutations generated by Sturmian words
• Permutation complexity of the Thue-Morse word

This page was built for publication: Permutation complexity and the letter doubling map

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2841975)