Infinite permutations of lowest maximal pattern complexity

DOI10.1016/J.TCS.2010.12.062MaRDI QIDQ544872zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 16 June 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Sturmian wordsubword complexityinfinite permutationSturmian permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

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.

Recommendations

• On periodicity and low complexity of infinite permutations
• On infinite permutations
• On the permutations generated by Sturmian words

Cites work

• A remark on morphic sturmian words
• Complexity of sequences and dynamical systems
• Language structure of pattern Sturmian words
• Maximal pattern complexity for discrete systems
• On periodicity and low complexity of infinite permutations
• On the permutations generated by Sturmian words
• Sequence entropy and the maximal pattern complexity of infinite words

Cited in

(16)

• Antimonotone permutations
• On the permutations generated by Sturmian words
• Permutation complexity and the letter doubling map
• Permutation complexity of the Thue-Morse word
• Canonical representatives of morphic permutations
• On automatic infinite permutations
• On periodicity and low complexity of infinite permutations
• Infinite words with linear subword complexity
• Infinite permutations vs. infinite words
• Factor complexity and permutation complexity of the generalized Morse sequence
• On a generalization of abelian equivalence and complexity of infinite words
• Sturmian words and the permutation that orders fractional parts
• Permutation complexity of images of Sturmian words by marked morphisms
• On infinite permutations
• Permutation complexity related to the letter doubling map
• Sequence entropy and the maximal pattern 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)