Permutation complexity of the Thue-Morse word
From MaRDI portal
Publication:550264
DOI10.1016/J.AAM.2010.08.002zbMATH Open1234.05012arXiv1003.6123OpenAlexW2037993261MaRDI QIDQ550264FDOQ550264
Authors: Steven Widmer 
Publication date: 8 July 2011
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Abstract: Given a countable set X (usually taken to be the natural numbers or the integers), an infinite permutation pi 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.
Full work available at URL: https://arxiv.org/abs/1003.6123
Recommendations
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Subword complexity of a generalized Thue-Morse word
- On an infinite permutation similar to the Thue-Morse word
- On the 2-abelian complexity of the Thue-Morse word
- The number of minimal word chains computing the Thue-Morse word
- Permutation complexity and the letter doubling map
- Factor complexity and permutation complexity of the generalized Morse sequence
- Abelian complexity of Thue-Morse word over a ternary alphabet
- Permutation complexity related to the letter doubling map
Cites Work
- Title not available (Why is that?)
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- On permutations generated by infinite binary words
- On the permutations generated by Sturmian words
- Enumeration of factors in the Thue-Morse word
- On periodicity and low complexity of infinite permutations
- Infinite permutations of lowest maximal pattern complexity
- On the infinite permutation generated by the period doubling word
Cited In (9)
- Enumeration and decidable properties of automatic sequences
- On automatic infinite permutations
- On an infinite permutation similar to the Thue-Morse word
- Factor complexity and permutation complexity of the generalized Morse sequence
- On the permutation complexity of the Cantor-like sequences
- Minimal complexity of equidistributed infinite permutations
- Permutation complexity and the letter doubling map
- Canonical Representatives of Morphic Permutations
- Title not available (Why is that?)
This page was built for publication: Permutation complexity of the Thue-Morse word
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q550264)
