Infinite permutations of lowest maximal pattern complexity (Q544872): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Sumit K. Garg / rank | |||
Normal rank | |||
Property / review text | |||
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\). | |||
Property / review text: 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\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Anton Černý / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5908421 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
infinite permutation | |||
Property / zbMATH Keywords: infinite permutation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
subword complexity | |||
Property / zbMATH Keywords: subword complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Sturmian word | |||
Property / zbMATH Keywords: Sturmian word / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Sturmian permutation | |||
Property / zbMATH Keywords: Sturmian permutation / rank | |||
Normal rank |
Revision as of 12:10, 1 July 2023
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