Infinite permutations of lowest maximal pattern complexity (Q544872): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2008695999 / rank | |||
Normal rank |
Revision as of 22:52, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Infinite permutations of lowest maximal pattern complexity |
scientific article |
Statements
Infinite permutations of lowest maximal pattern complexity (English)
0 references
16 June 2011
0 references
An \(\mathbb{N}\)-permutation is a linear ordering of \(\mathbb{N}\) represented by \ a sequence of pairwise distinct real numbers \(\alpha=\left\{ \alpha _{i}\right\} _{i=1}^{\infty}\).\ The ordering may be encoded using the symbols \(\gamma_{ij}\in\left\{ <,>\right\} \), where \(\gamma_{ij}=\,<\) if \(\alpha _{i}<\alpha_{j}\), and \(\gamma_{ij}=\,>\) otherwise. The sequence \(\alpha\) is [ultimately] periodic if, for some \(t\geq1,\) \(\gamma_{ij}=\gamma_{i+tj+t}\) for all \(i,j\) (starting from some \(n_{0}\)). A \(T\)-pattern in \(\alpha\), where \(T=\left\{ 0<m_{1}<\cdots<m_{n-1}\right\} \), is the \(n\)-permutation corresponding to a finite subsequence \(\alpha_{k}\alpha_{m_{1}+k}\cdots \alpha_{m_{n-1}+k}\), \(k\geq0\). The number of distinct \(T\)-patterns in \(\alpha\) is denoted as \(p_{\alpha}\left( T\right) \). A \(\left\{ 0,1,\ldots,n-1\right\} \)-pattern\ in \(\alpha\) is called an \(n\)-factor of \(\alpha\). A characterization of (ultimate) periodicity of \(\mathbb{N}\)-permutations based on the number \(f_{\alpha}\left( n\right) \) of distinct factors of \(\alpha\) of length \(n\) is known and just partially corresponds to the similar characterization for infinite words. In the current paper the authors consider the maximal pattern complexity \(p_{\alpha}^{\ast}\left( n\right) =\max_{\left| T\right| =n}p_{\alpha}\left( T\right).\) Their main result states that an infinite word is ultimately periodic if and only if \(p_{\alpha}^{\ast}\left( n\right) \geq n\). This is an analogue of a similar fact known for infinite words (where the right-hand side is to be replaced by \(2n\)). Moreover, they prove that equality holds exactly for those \(\mathbb{N}\)-permutations that are Sturmian. An \(\mathbb{N}\)-permutation \(\alpha\) is said to be Sturmian if it can be described using some Sturmian word \(w=w_{0}w_{1}\cdots\) and fixed real numbers \(\alpha_{0},x,y\) by the formula \(\alpha_{i+1}=\alpha_{i}+x\) if \(w_{i}=0\) and \(\alpha_{i+1}=\alpha_{i}-y\) if \(w_{i}=1\).
0 references
infinite permutation
0 references
subword complexity
0 references
Sturmian word
0 references
Sturmian permutation
0 references