Infinite permutations of lowest maximal pattern complexity (Q544872): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
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 / 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 | |||
Property / reviewed by | |||
Property / reviewed by: Anton Černý / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2008695999 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0910.5696 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A remark on morphic sturmian words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of sequences and dynamical systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On periodicity and low complexity of infinite permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Language structure of pattern Sturmian words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sequence entropy and the maximal pattern complexity of infinite words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maximal pattern complexity for discrete systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5391598 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 04:47, 4 July 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