Infinite permutations of lowest maximal pattern complexity
From MaRDI portal
Publication:544872
DOI10.1016/J.TCS.2010.12.062zbMATH Open1232.68095arXiv0910.5696OpenAlexW2008695999MaRDI QIDQ544872FDOQ544872
Authors: Yong-Cai Geng, Sumit K. Garg 
Publication date: 16 June 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: An infinite permutation is a linear ordering of the set of non-negative integers. Generally, the properties of infinite permutations analogous to those of infinite words show some resemblances and some differences between permutations and words. In this paper, we define maximal pattern complexity for infinite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic. Then we characterize the non-periodic permutations of minimal complexity (equal to n) and find that they all are constructed with the use of Sturmian words.
Full work available at URL: https://arxiv.org/abs/0910.5696
Recommendations
Cites Work
- On the permutations generated by Sturmian words
- Sequence entropy and the maximal pattern complexity of infinite words
- Maximal pattern complexity for discrete systems
- On periodicity and low complexity of infinite permutations
- A remark on morphic sturmian words
- Complexity of sequences and dynamical systems
- Language structure of pattern Sturmian words
Cited In (17)
- On automatic infinite permutations
- Permutation complexity of images of Sturmian words by marked morphisms
- Infinite permutations vs. infinite words
- Permutation complexity of the Thue-Morse word
- On periodicity and low complexity of infinite permutations
- Antimonotone permutations
- Ergodic infinite permutations of minimal complexity
- Canonical representatives of morphic permutations
- Sequence entropy and the maximal pattern complexity of infinite words
- On the permutations generated by Sturmian words
- Infinite words with linear subword complexity
- Factor complexity and permutation complexity of the generalized Morse sequence
- Permutation complexity related to the letter doubling map
- Permutation complexity and the letter doubling map
- Sturmian words and the permutation that orders fractional parts
- On infinite permutations
- On a generalization of abelian equivalence and complexity of infinite words
This page was built for publication: Infinite permutations of lowest maximal pattern complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q544872)
