シフトスペース

記号力学および関連する数学分野において、シフト空間または部分シフトとは、離散システムの進化を表す無限個の語の集合である。実際、シフト空間と記号力学系はしばしば同義語とみなされる。最も広く研究されているシフト空間は、有限型部分シフトとソフィックシフトである。

古典的な枠組み^{[ 1 ]}では、シフト空間は任意のサブセットである。${\displaystyle \Lambda }$の${\displaystyle A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}}$、 どこ${\displaystyle A}$は有限集合であり、ティホノフ位相に関して閉じており、並進不変である。より一般的には、シフト空間を、 の閉じた並進不変な部分集合として定義することができる。${\displaystyle A^{\mathbb {G} }}$、 どこ${\displaystyle A}$は任意の空でない集合であり、${\displaystyle \mathbb {G} }$は任意のモノイドである。^{[ 2 ] [ 3 ]}

させて${\displaystyle \mathbb {G} }$モノイドであり、与えられた${\displaystyle g,h\in \mathbb {G} }$、 の操作を表す${\displaystyle g}$と${\displaystyle h}$製品によって${\displaystyle gh}$。 させて$\displaystyle \mathbf {1} _{\mathbb {G}}$の同一性を表す${\displaystyle \mathbb {G} }$空でない集合を考える${\displaystyle A}$離散トポロジーを持つ（アルファベット）を定義し、${\displaystyle A^{\mathbb {G} }}$すべてのパターンの集合として${\displaystyle A}$インデックス${\displaystyle \mathbb {G} }$。 のために${\displaystyle \mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }}$そしてその部分集合${\displaystyle N\subset \mathbb {G} }$、の制限を表す${\displaystyle \mathbf {x} }$のインデックスへ${\displaystyle N}$として${\displaystyle \mathbf {x} _{N}:=(x_{i})_{i\in N}}$。

の上${\displaystyle A^{\mathbb {G} }}$我々はプロディスクリプティブ位相を考察する。${\displaystyle A^{\mathbb {G} }}$ハウスドルフ空間と完全に不連結な位相空間の場合。${\displaystyle A}$有限であることから、${\displaystyle A^{\mathbb {G} }}$コンパクトです。ただし、${\displaystyle A}$有限でない場合、${\displaystyle A^{\mathbb {G} }}$局所的にコンパクトですらない。

このトポロジーは、以下の場合に限りメートル化可能になります。${\displaystyle \mathbb {G} }$は可算であり、いずれにしても、この位相の基底は、次のように定義される開集合/閉集合（シリンダーと呼ばれる）の集合から構成されます。有限個のインデックスの集合が与えられた場合${\displaystyle D\subset \mathbb {G} }$、そしてそれぞれについて${\displaystyle i\in D}$、 させて${\displaystyle a_{i}\in A}$シリンダーは次のように与えられます。${\displaystyle D}$そして${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$セットは

${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.}$

いつ${\displaystyle D=\{g\}}$円筒を固定する記号で表す${\displaystyle b}$インデックス付きのエントリで${\displaystyle g}$単純に${\displaystyle [b]_{g}}$。

つまり、円筒形の${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}}$すべての無限パターンの集合です${\displaystyle A^{\mathbb {G} }}$有限パターンを含む${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$。

与えられた${\displaystyle g\in \mathbb {G} }$gシフトマップ​${\displaystyle A^{\mathbb {G} }}$は、${\displaystyle \sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }}$そして次のように定義される

${\displaystyle \sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }}$。

アルファベットの上にスペースを移動${\displaystyle A}$セット${\displaystyle \Lambda \subset A^{\mathbb {G} }}$それは、${\displaystyle A^{\mathbb {G} }}$また、並進に対して不変である、すなわち、${\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda }$すべての人々のために${\displaystyle g\in \mathbb {G} }$[^{注1 ]}シフト空間では${\displaystyle \Lambda }$誘導されたトポロジー${\displaystyle A^{\mathbb {G} }}$シリンダーを基本開放セットとする${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda }$。

各${\displaystyle k\in \mathbb {N} ^{*}}$、 定義する${\displaystyle {\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}}$、 そして${\displaystyle {\mathcal {N}}_{A^{\mathbb {G} }}^{f}:=\bigcup _{k\in \mathbb {N} }{\mathcal {N}}_{k}=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }A^{N}}$シフト空間を定義する同等の方法は、禁止パターンの集合を取ることである。${\displaystyle F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}}$そしてシフト空間を集合として定義する

${\displaystyle X_{F}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ \forall N\subset \mathbb {G} ,\forall g\in \mathbb {G} ,\ \left(\sigma ^{g}(\mathbf {x} )\right)_{N}=\mathbf {x} _{gN}\notin F\}.}$

直感的に、シフトスペース${\displaystyle X_{F}}$は、禁止されている有限パターンを含まないすべての無限パターンの集合です。${\displaystyle F}$。

シフト空間が与えられた場合${\displaystyle \Lambda \subset A^{\mathbb {G} }}$そして有限個のインデックス${\displaystyle N\subset \mathbb {G} }$、 させて${\displaystyle W_{\emptyset }(\Lambda ):=\{\epsilon \}}$、 どこ${\displaystyle \epsilon }$は空語を表し、${\displaystyle N\neq \emptyset }$させて ${\displaystyle W_{N}(\Lambda )\subset A^{N}}$すべての有限構成の集合とする${\displaystyle A^{N}}$何らかの順序で現れる${\displaystyle \Lambda }$つまり、

${\displaystyle W_{N}(\Lambda ):=\{(w_{i})_{i\in N}\in A^{N}:\ \exists \ \mathbf {x} \in \Lambda {\text{ s.t. }}x_{i}=w_{i}\ \forall i\in N\}.}$

注意すべき点として、${\displaystyle \Lambda }$シフト空間である場合、${\displaystyle M\subset \mathbb {G} }$は${\displaystyle N\subset \mathbb {G} }$つまり、${\displaystyle M=gN}$一部の人にとって${\displaystyle g\in \mathbb {G} }$、 それから${\displaystyle (w_{j})_{j\in M}\in W_{M}(\Lambda )}$存在する場合に限り${\displaystyle (v_{i})_{i\in N}\in W_{N}(\Lambda )}$そのため${\displaystyle w_{j}=v_{i}}$もし${\displaystyle j=gi}$。 言い換えると、${\displaystyle W_{M}(\Lambda )}$そして${\displaystyle W_{N}(\Lambda )}$変換を除いて同じ構成を含む。このセットを

${\displaystyle W(\Lambda ):=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }W_{N}(\Lambda )}$

言語​​${\displaystyle \Lambda }$ここで述べた一般的な文脈では、シフト空間の言語は形式言語理論における意味とは異なり、アルファベットを考慮する古典的な枠組みにおける意味と同じである。${\displaystyle A}$有限であり、${\displaystyle \mathbb {G} }$いる${\displaystyle \mathbb {N} }$または${\displaystyle \mathbb {Z} }$通常の追加事項を除けば、シフト空間の言語は形式言語である。

シフト空間の古典的な枠組みは、アルファベットを考慮することから成る。${\displaystyle A}$有限であり、${\displaystyle \mathbb {G} }$非負整数の集合として（${\displaystyle \mathbb {N} }$) 通常の加算、またはすべての整数の集合 (${\displaystyle \mathbb {Z} }$通常の加算と合わせて、どちらの場合も、単位元は${\displaystyle \mathbf {1} _{\mathbb {G} }}$0 という数に対応します。さらに、${\displaystyle \mathbb {G} =\mathbb {N} }$すべて${\displaystyle \mathbb {N} \setminus \{0\}}$1 から生成できる、次の一意のシフト マップを考慮すれば十分である。${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$すべての人々のために${\displaystyle n}$一方、${\displaystyle \mathbb {G} =\mathbb {Z} }$すべて${\displaystyle \mathbb {Z} }$は数値 {-1, 1} から生成できます。すべての に対して与えられた 2 つのシフト マップを考慮するだけで十分です。${\displaystyle n}$による${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$そして${\displaystyle \sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}}$。

さらに、${\displaystyle \mathbb {G} }$は${\displaystyle \mathbb {N} }$または${\displaystyle \mathbb {Z} }$通常の追加（濃度とは無関係に） ${\displaystyle A}$）代数構造のため、次の形式の円柱のみを考慮すれば十分である。

${\displaystyle [a_{0}a_{1}...a_{n}]:=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.}$

さらに、シフト空間の言語 ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$によって与えられる

${\displaystyle W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),}$

どこ${\displaystyle W_{0}:=\{\epsilon \}}$そして${\displaystyle \epsilon }$は空虚な言葉を表し、

${\displaystyle W_{n}(\Lambda ):=\{((a_{i})_{i=0,..n}\in A^{n}:\ \exists \mathbf {x} \in \Lambda \ s.t.\ x_{i}=a_{i}\ \forall i=0,...,n\}.}$

同様に、${\displaystyle \mathbb {G} =\mathbb {Z} }$したがって、シフト空間を定義するには${\displaystyle \Lambda =X_{F}}$インデックスを指定する必要はありません${\displaystyle \mathbb {G} }$禁じられた言葉${\displaystyle F}$定義されています。つまり、 ${\displaystyle F\subset \bigcup _{n\geq 1}A^{n}}$その後

${\displaystyle X_{F}=\{\mathbb {x} \in A^{\mathbb {Z} }:\ \forall i\in \mathbb {Z} ,\ \forall k\geq 0,\ (x_{i}...x_{i+k})\notin F\}.}$

しかし、もし${\displaystyle \mathbb {G} =\mathbb {N} }$シフト空間を定義すると${\displaystyle \Lambda =X_{F}}$上記のように、単語が禁止されているインデックスを指定しない場合、シフトマップを通じて不変なシフト空間をキャプチャします。つまり、${\displaystyle \sigma (X_{F})=X_{F}}$実際、シフト空間を定義するには${\displaystyle X_{F}\subset A^{\mathbb {N} }}$そのため${\displaystyle \sigma (X_{F})\subsetneq X_{F}}$どのインデックスから単語を指定する必要があるか${\displaystyle F}$禁止されています。

特に、古典的な枠組みでは${\displaystyle A}$有限であり、${\displaystyle \mathbb {G} }$いる${\displaystyle \mathbb {N} }$） または${\displaystyle \mathbb {Z} }$通常の追加を加えると、次のようになる。${\displaystyle M_{F}}$有限であるのは、${\displaystyle F}$は有限であり、それによって有限型のシフトの古典的な定義が導かれる。${\displaystyle \Lambda \subset A^{\mathbb {G} }}$そのため${\displaystyle \Lambda =X_{F}}$ある有限の${\displaystyle F}$。

いくつかの種類のシフト空間の中で、最も広く研究されているのは有限型シフトとソフィックシフトである。

アルファベットの場合${\displaystyle A}$有限であり、シフト空間である${\displaystyle \Lambda }$有限個の禁止パターンを取れば、それは有限型のシフトである。${\displaystyle F}$そのため${\displaystyle \Lambda =X_{F}}$、 そして${\displaystyle \Lambda }$は、スライディングブロックコード^{[ 1 ]}の下での有限型シフトの像である場合、ソフィックシフトである（つまり、マップ${\displaystyle \Phi }$これはすべての人にとって連続かつ不変である${\displaystyle g}$-シフトマップ)。${\displaystyle A}$有限であり${\displaystyle \mathbb {G} }$は${\displaystyle \mathbb {N} }$または${\displaystyle \mathbb {Z} }$通常の加算に加えて、シフト${\displaystyle \Lambda }$ソフィックシフトであるのは、${\displaystyle W(\Lambda )}$は正規言語です。

「ソフィック」という名称は、有限性の性質の一般化を指すために、ヘブライ語のסופי（有限）に基づいてワイス（1973）によって造語された。 ^{[ 4 ]}

いつ${\displaystyle A}$無限である場合、有限型のシフトをシフト空間として定義することが可能です。${\displaystyle \Lambda }$それらのセットを取ることができます${\displaystyle F}$禁止語の $${\displaystyle M_{F}:=\{g\in \mathbb {G}$$ :\ \exists N\subset \mathbb {G} {\text{ st }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\}} は有限であり、${\displaystyle \Lambda =X_{F}}$^{[ 3 ]}無限アルファベットのこの文脈では、ソフィックシフトは、特定のクラスのスライディングブロックコードの下での有限型のシフトの像として定義されます。^{[ 3 ]}有限性と${\displaystyle M_{F}}$また、スライディングブロックコードの追加条件は、次の場合に自明に満たされます。${\displaystyle A}$有限である。

シフト空間とは、記号力学系が通常定義される位相空間のことである。

シフト空間が与えられた場合${\displaystyle \Lambda \subset A^{\mathbb {G} }}$そして${\displaystyle g}$-シフトマップ${\displaystyle \sigma ^{g}:\Lambda \to \Lambda }$したがって、ペアは${\displaystyle (\Lambda ,\sigma ^{g})}$これは位相力学系である。

2つのシフトスペース${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ そして${\displaystyle \Gamma \subset B^{\mathbb {G} }}$ 各 に対して が位相的に共役（または単に共役）であると言われるのは、${\displaystyle g}$-シフトマップは、位相力学系が${\displaystyle (\Lambda ,\sigma ^{g})}$そして${\displaystyle (\Gamma ,\sigma ^{g})}$位相的に共役である、つまり連続写像が存在する場合${\displaystyle \Phi$ :\Lambda \to \Gamma } で、 ${\displaystyle \Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi }$このようなマップは、一般化スライディングブロックコードまたは単にスライディングブロックコードとして知られています。${\displaystyle \Phi }$一様に連続である。^{[ 3 ]}

連続マップ${\displaystyle \Phi }$から${\displaystyle \Lambda \subset A^{\mathbb {G} }}$それ自体が位相力学系を定義する${\displaystyle (\Lambda ,\Phi )}$記号力学では、連続写像のみを考慮するのが一般的である。${\displaystyle \Phi$ :\Lambda \to \Lambda } はすべての と可換です${\displaystyle g}$-シフトマップ、すなわち、一般化スライディングブロックコードであるマップ。動的システム${\displaystyle (\Lambda ,\Phi )}$「一般化セルオートマトン」として知られています（または単にセルオートマトンとも呼ばれます）。${\displaystyle \Phi }$（一様連続である）。

シフト空間（有限型）の最初の自明な例は、フルシフトである。${\displaystyle A^{\mathbb {N} }}$。

させて${\displaystyle A=\{a,b\}}$。A上のすべての無限語のうち、b を最大で 1 つ含むものは、有限型ではなく、ソフィック部分シフトである。A上のすべての無限語のうち、bが素数長のブロックを形成するものは、ソフィックではない（これはポンピング補題を用いて示すことができる）。

2文字で表す無限の文字列の空間、${\displaystyle \{0,1\}^{\mathbb {N} }}$これはベルヌーイ過程と呼ばれ、カントール集合と同型である。

2文字の文字列の双無限空間、${\displaystyle \{0,1\}^{\mathbb {Z} }}$これは一般的にベイカーの地図として知られているが、正確にはベイカーの地図と同型である。

• テントマップ
• ビットシフトマップ
• グレーコード

• Ceccherini-Silberstein, T.; Coornaert, M. (2010). Cellular automata and groups Springer Monographs in Mathematics . Springer Verlag. ISBN 978-3-642-14034-1。
• リンド、ダグラス、マ​​ーカス、ブライアン（1995）。『記号力学と符号化入門』ケンブリッジ（英国）：ケンブリッジ大学出版局。ISBN 0-521-55900-6。
• ロテール、M. (2002). 「有限語と無限語」 . 『語の代数的組み合わせ論』. ケンブリッジ、英国：ケンブリッジ大学出版局. ISBN 0-521-81220-82008年1月29日に取得。
• Morse, Marston ; Hedlund, Gustav A. (1938). "Symbolic Dynamics". American Journal of Mathematics . 60 (4): 815– 866. doi : 10.2307/2371264 . JSTOR 2371264 . 
• Sobottka, M. (2022). "シフト空間の分類に関するいくつかの注記: 有限型シフト、ソフィックシフト、および有限定義シフト". Bulletin of the Brazilian Mathematical Society . New Series. 53 (3): 981– 1031. arXiv : 2010.10595 . doi : 10.1007/s00574-022-00292-x . S2CID 254048586 .