Set of infinite words
記号力学および関連する 数学 分野 において 、 シフト空間 または サブシフトとは、 離散系 の発展を表す 無限 語 の集合である 。実際、シフト空間と 記号力学系は しばしば同義語 とみなされる 。最も広く研究されているシフト空間は、 有限型のサブシフト とソフィックシフトである。
古典的な枠組み [1] において、シフト空間とは の任意の部分集合であり 、は 有限集合 であり 、ティコノフ位相に対して閉じており、並進不変である。より一般的には、シフト空間は の閉じた並進不変な部分集合として定義することができ 、は任意の空 でない集合であり、は任意の モノイド である 。 [2] [3] Λ {\displaystyle \Lambda } A Z := { ( x i ) i ∈ Z : x i ∈ A ∀ i ∈ Z } {\displaystyle A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}} A {\displaystyle A} A G {\displaystyle A^{\mathbb {G} }} A {\displaystyle A} G {\displaystyle \mathbb {G} }
意味 を モノイド と し、 が与えられたとき、 の積 による 演算を で表します 。を の恒等式 で表します。 離散位相 を 持つ空でない集合 (アルファベット)を考え 、を で 添字付けされた 上 のすべてのパターンの集合 と定義します。 と部分集合 について、 の 添字へ の の制限を で表します 。 G {\displaystyle \mathbb {G} } g , h ∈ G {\displaystyle g,h\in \mathbb {G} } g {\displaystyle g} h {\displaystyle h} g h {\displaystyle gh} 1 G {\displaystyle \mathbf {1} _{\mathbb {G} }} G {\displaystyle \mathbb {G} } A {\displaystyle A} A G {\displaystyle A^{\mathbb {G} }} A {\displaystyle A} G {\displaystyle \mathbb {G} } x = ( x i ) i ∈ G ∈ A G {\displaystyle \mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }} N ⊂ G {\displaystyle N\subset \mathbb {G} } x {\displaystyle \mathbf {x} } N {\displaystyle N} x N := ( x i ) i ∈ N {\displaystyle \mathbf {x} _{N}:=(x_{i})_{i\in N}}
において 、ハウスドルフかつ全不連続な位相空間を形成するプロ離散位相を考える 。 が有限である場合 、 は コンパクトとなる。しかし、 が有限でない場合、 は 局所コンパクトでさえない。 A G {\displaystyle A^{\mathbb {G} }} A G {\displaystyle A^{\mathbb {G} }} A {\displaystyle A} A G {\displaystyle A^{\mathbb {G} }} A {\displaystyle A} A G {\displaystyle A^{\mathbb {G} }}
この位相は、 が可算な場合のみ計量化可能であり 、いずれにしても、この位相の基底は、次のように定義される開集合/閉集合(シリンダーと呼ばれる)の集合で構成される。 、 の有限集合が与えられ 、各 に対して と おく 。 と によって与えられる シリンダー は、集合 G {\displaystyle \mathbb {G} } D ⊂ G {\displaystyle D\subset \mathbb {G} } i ∈ D {\displaystyle i\in D} a i ∈ A {\displaystyle a_{i}\in A} D {\displaystyle D} ( a i ) i ∈ D ∈ A | D | {\displaystyle (a_{i})_{i\in D}\in A^{|D|}}
[ ( a i ) i ∈ D ] D := { x ∈ A G : x i = a i , ∀ i ∈ D } . {\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.} のとき、 でインデックスされたエントリに シンボルを固定するシリンダーを 単にと表します 。 D = { g } {\displaystyle D=\{g\}} b {\displaystyle b} g {\displaystyle g} [ b ] g {\displaystyle [b]_{g}}
言い換えれば、円筒は 有限パターンを含む すべての無限パターンの集合の集合です 。 [ ( a i ) i ∈ D ] D {\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}} A G {\displaystyle A^{\mathbb {G} }} ( a i ) i ∈ D ∈ A | D | {\displaystyle (a_{i})_{i\in D}\in A^{|D|}}
が与えられたとき 、 上の g シフト写像 は で表され 、次のように定義される。 g ∈ G {\displaystyle g\in \mathbb {G} } A G {\displaystyle A^{\mathbb {G} }} σ g : A G → A G {\displaystyle \sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }}
σ g ( ( x i ) i ∈ G ) = ( x g i ) i ∈ G {\displaystyle \sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }} 。 アルファベット上の シフト 空間 は、 の位相で閉じられており 、変換で不変である、つまり すべての に対して である 集合です 。 [注 1] シフト空間において、 から誘導された位相を考えます。 この位相では、シリンダー が基本開集合として存在します 。 A {\displaystyle A} Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }} A G {\displaystyle A^{\mathbb {G} }} σ g ( Λ ) ⊂ Λ {\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda } g ∈ G {\displaystyle g\in \mathbb {G} } Λ {\displaystyle \Lambda } A G {\displaystyle A^{\mathbb {G} }} [ ( a i ) i ∈ D ] Λ := [ ( a i ) i ∈ D ] ∩ Λ {\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda }
各 に対して 、 、 と を定義する。シフト空間を定義するのと同等の方法は、 禁制パターン の集合を取り 、シフト空間を集合として定義する
ことである。 k ∈ N ∗ {\displaystyle k\in \mathbb {N} ^{*}} N k := ⋃ N ⊂ G # N = k A N {\displaystyle {\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}} N A G f := ⋃ k ∈ N N k = ⋃ N ⊂ G # N < ∞ 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}} F ⊂ N A G f {\displaystyle F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}}
X F := { x ∈ A G : ∀ N ⊂ G , ∀ g ∈ G , ( σ g ( x ) ) N = x g N ∉ 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\}.} 直感的に言えば、シフト空間は の禁制の有限パターンを含まないすべての無限パターンの集合です 。 X F {\displaystyle X_{F}} F {\displaystyle F}
シフトスペースの言語 シフト空間 と有限の添え字集合 が与えられたとき 、 とする。 ここで は 空語 を表し、 は のシーケンスに現れる のすべての有限構成の集合とする。 すなわち 、 Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }} N ⊂ G {\displaystyle N\subset \mathbb {G} } W ∅ ( Λ ) := { ϵ } {\displaystyle W_{\emptyset }(\Lambda ):=\{\epsilon \}} ϵ {\displaystyle \epsilon } N ≠ ∅ {\displaystyle N\neq \emptyset } W N ( Λ ) ⊂ A N {\displaystyle W_{N}(\Lambda )\subset A^{N}} A N {\displaystyle A^{N}} Λ {\displaystyle \Lambda }
W N ( Λ ) := { ( w i ) i ∈ N ∈ A N : ∃ x ∈ Λ s.t. x i = w i ∀ i ∈ N } . {\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 } M ⊂ G {\displaystyle M\subset \mathbb {G} } N ⊂ G {\displaystyle N\subset \mathbb {G} } M = g N {\displaystyle M=gN} g ∈ G {\displaystyle g\in \mathbb {G} } ( w j ) j ∈ M ∈ W M ( Λ ) {\displaystyle (w_{j})_{j\in M}\in W_{M}(\Lambda )} ( v i ) i ∈ N ∈ W N ( Λ ) {\displaystyle (v_{i})_{i\in N}\in W_{N}(\Lambda )} w j = v i {\displaystyle w_{j}=v_{i}} j = g i {\displaystyle j=gi} W M ( Λ ) {\displaystyle W_{M}(\Lambda )} W N ( Λ ) {\displaystyle W_{N}(\Lambda )}
W ( Λ ) := ⋃ N ⊂ G # N < ∞ W N ( Λ ) {\displaystyle W(\Lambda ):=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }W_{N}(\Lambda )} の 言語 。ここで述べた一般的な文脈では、シフト空間の言語は 形式言語理論 における言語と同じ意味を持たないが、アルファベットが 有限であり、または 通常の追加でで あると考える古典的 な 枠組みでは、シフト空間の言語は形式言語である。 Λ {\displaystyle \Lambda } A {\displaystyle A} G {\displaystyle \mathbb {G} } N {\displaystyle \mathbb {N} } Z {\displaystyle \mathbb {Z} }
古典的な枠組み シフト空間の古典的な枠組みは、アルファベットを 有限なものとし、 通常の加算を伴う 非負整数の集合 ( )、または 通常の加算を伴うすべての整数の集合 ( ) と考えることから成ります。どちらの場合も、単位元は 数 0 に対応します。さらに、 のとき 、すべては 数 1 から生成できるため、 すべての に対してによって与えられる一意のシフト マップを考えれば十分です 。一方、 のときは 、すべては数 {-1, 1} から生成できるため、すべて に対してによって 、また によって 与えられる 2 つのシフト マップを考えれば十分です 。 A {\displaystyle A} G {\displaystyle \mathbb {G} } N {\displaystyle \mathbb {N} } Z {\displaystyle \mathbb {Z} } 1 G {\displaystyle \mathbf {1} _{\mathbb {G} }} G = N {\displaystyle \mathbb {G} =\mathbb {N} } N ∖ { 0 } {\displaystyle \mathbb {N} \setminus \{0\}} σ ( x ) n = x n + 1 {\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}} n {\displaystyle n} G = Z {\displaystyle \mathbb {G} =\mathbb {Z} } Z {\displaystyle \mathbb {Z} } n {\displaystyle n} σ ( x ) n = x n + 1 {\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}} σ − 1 ( x ) n = x n − 1 {\displaystyle \sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}}
さらに、 が、あるいは の 基数 とは無関係に通常の加算で 、その代数構造により、 の形の円筒のみを考えれば十分である。 G {\displaystyle \mathbb {G} } N {\displaystyle \mathbb {N} } Z {\displaystyle \mathbb {Z} } A {\displaystyle A}
[ a 0 a 1 . . . a n ] := { ( x i ) i ∈ G : x i = a i ∀ i = 0 , . . , n } . {\displaystyle [a_{0}a_{1}...a_{n}]:=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.} さらに、シフト空間の言語は 次のように与えられる。 Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }}
W ( Λ ) := ⋃ n ≥ 0 W n ( Λ ) , {\displaystyle W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),} ここで 、and は空語を表し、 W 0 := { ϵ } {\displaystyle W_{0}:=\{\epsilon \}} ϵ {\displaystyle \epsilon }
W n ( Λ ) := { ( ( a i ) i = 0 , . . n ∈ A n : ∃ x ∈ Λ s . t . x i = a i ∀ i = 0 , . . . , n } . {\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\}.} 同様に、 の特別なケースでは 、シフト空間を定義するために、 の禁制語が定義されている の インデックスを指定する必要がないことが分かります 。つまり、 と
を考えるだけで済みます。 G = Z {\displaystyle \mathbb {G} =\mathbb {Z} } Λ = X F {\displaystyle \Lambda =X_{F}} G {\displaystyle \mathbb {G} } F {\displaystyle F} F ⊂ ⋃ n ≥ 1 A n {\displaystyle F\subset \bigcup _{n\geq 1}A^{n}}
X F = { x ∈ A Z : ∀ i ∈ Z , ∀ k ≥ 0 , ( x i . . . x i + k ) ∉ F } . {\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\}.} しかし、 の場合 、 のインデックスを指定せずに上記のように シフト空間を定義すると、 となるシフト写像を通して不変なシフト空間、つまり となるシフト空間を捉えることになります 。実際、 となるシフト空間を定義するには、 のどのインデックスから の単語が禁止される かを指定する必要があります 。 G = N {\displaystyle \mathbb {G} =\mathbb {N} } Λ = X F {\displaystyle \Lambda =X_{F}} σ ( X F ) = X F {\displaystyle \sigma (X_{F})=X_{F}} X F ⊂ A N {\displaystyle X_{F}\subset A^{\mathbb {N} }} σ ( X F ) ⊊ X F {\displaystyle \sigma (X_{F})\subsetneq X_{F}} F {\displaystyle F}
特に、 が有限で あり である ) という古典的な枠組み、または 通常の追加により、 が有限である 場合に限り が有限であることが証明され、これは、 ある有限 に対して となる シフト空間としての有限型のシフトの古典的な定義につながり ます 。 A {\displaystyle A} G {\displaystyle \mathbb {G} } N {\displaystyle \mathbb {N} } Z {\displaystyle \mathbb {Z} } M F {\displaystyle M_{F}} F {\displaystyle F} Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }} Λ = X F {\displaystyle \Lambda =X_{F}} F {\displaystyle F}
シフトスペースの種類 いくつかのタイプのシフト空間の中で、最も広く研究されているのは 有限タイプのシフト とソフィックシフトです。
アルファベットが有限の場合、 となる 禁制パターンの有限集合を取ることができるとき シフト空間は 有限型のシフト で あり、 はスライディングブロックコード [1] の下で有限型のシフトの像であるとき (つまり、 すべての -シフト写像 に対して連続かつ不変な写像 )、 は ソフィックシフト である。 が有限で または 通常の加算で で ある とき、 は 正規言語 である 場合に限り、 シフトはソフィックシフトである 。 A {\displaystyle A} Λ {\displaystyle \Lambda } F {\displaystyle F} Λ = X F {\displaystyle \Lambda =X_{F}} Λ {\displaystyle \Lambda } Φ {\displaystyle \Phi } g {\displaystyle g} A {\displaystyle A} G {\displaystyle \mathbb {G} } N {\displaystyle \mathbb {N} } Z {\displaystyle \mathbb {Z} } Λ {\displaystyle \Lambda } W ( Λ ) {\displaystyle W(\Lambda )}
「ソフィック」という名前は、ワイス(1973)が「有限」を意味する ヘブライ 語のסופיに基づいて作ったもので、有限性の性質の一般化であることを示しています。 [4]
が無限大のとき 、有限型のシフトをシフト空間として定義することができ、 次のような禁制語の 集合をとることができる。 A {\displaystyle A} Λ {\displaystyle \Lambda } F {\displaystyle F}
M F := { g ∈ G : ∃ N ⊂ G s.t. g ∈ N and ( w i ) i ∈ N ∈ F } , {\displaystyle M_{F}:=\{g\in \mathbb {G} :\ \exists N\subset \mathbb {G} {\text{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},} は有限であり、である 。 [3] この無限アルファベットの文脈では、ソフィックシフトは、特定のクラスのスライディングブロックコードの下での有限タイプのシフトの像として定義される。 [3] の 有限性 とスライディングブロックコードの追加条件は、 が有限である場合はいつでも自明に満たされる。 Λ = X F {\displaystyle \Lambda =X_{F}} M F {\displaystyle M_{F}} A {\displaystyle A}
シフト空間上の位相力学系 シフト空間は、 記号的動的システム が通常定義される 位相空間 です。
シフト空間 と -シフト マップが与えられれば、そのペアは 位相的動的システム である ことがわかります 。 Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }} g {\displaystyle g} σ g : Λ → Λ {\displaystyle \sigma ^{g}:\Lambda \to \Lambda } ( Λ , σ g ) {\displaystyle (\Lambda ,\sigma ^{g})}
2つのシフト空間 とが 位相共役(あるいは単に共役)であるとは、各 -シフト写像に対して位相力学系 とが 位相共役 となること 、すなわち、と なる 連続写像が存在することを指す。このような写像は、が一様連続である ときはいつでも、 一般化スライディングブロック符号 、あるいは単に スライディングブロック符号 と呼ばれる 。 [3] Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }} Γ ⊂ B G {\displaystyle \Gamma \subset B^{\mathbb {G} }} g {\displaystyle g} ( Λ , σ g ) {\displaystyle (\Lambda ,\sigma ^{g})} ( Γ , σ g ) {\displaystyle (\Gamma ,\sigma ^{g})} Φ : Λ → Γ {\displaystyle \Phi :\Lambda \to \Gamma } Φ ∘ σ g = σ g ∘ Φ {\displaystyle \Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi } Φ {\displaystyle \Phi }
からへの 任意の連続写像は 位相力学系 を定義するが 、記号力学では、 すべての - シフト写像と可換な連続写像、すなわち一般化スライディングブロックコードである写像のみを考慮するのが一般的である。この力学系は 「 一般化セルオートマトン」 (または が一様連続である 場合は単に セルオートマトン )として知られている。 Φ {\displaystyle \Phi } Λ ⊂ A G {\displaystyle \Lambda \subset A^{\mathbb {G} }} ( Λ , Φ ) {\displaystyle (\Lambda ,\Phi )} Φ : Λ → Λ {\displaystyle \Phi :\Lambda \to \Lambda } g {\displaystyle g} ( Λ , Φ ) {\displaystyle (\Lambda ,\Phi )} Φ {\displaystyle \Phi }
例 シフト空間(有限型)の最初の簡単な例は、 フルシフト です。 A N {\displaystyle A^{\mathbb {N} }}
とする。A 上 のすべての無限語のうち、 最大で1つの bを含むものは、有限型ではなく、ソフィックな部分シフトである。A 上 のすべての無限語のうち、 b が素数長のブロックを形成するものは、ソフィックではない(これは ポンピング補題 を用いて示せる )。 A = { a , b } {\displaystyle A=\{a,b\}}
2文字の無限弦の空間は ベルヌーイ過程 と呼ばれる 。これは カントール集合 と同型である。 { 0 , 1 } N {\displaystyle \{0,1\}^{\mathbb {N} }}
2 つの文字の文字列の双無限空間は、一般に ベイカー マップ として知られており 、ベイカー マップと準同型です。 { 0 , 1 } Z {\displaystyle \{0,1\}^{\mathbb {Z} }}
参照
^ シフト空間 を指す場合、単に 「シフト」 または 「サブシフト」 という表現が一般的です。しかし、一部の著者は、-シフト写像 に対して不変である無限パターンの集合に対して 「シフト」 および 「サブシフト」 という用語を使用し 、プロ離散位相に対しても閉じている無限パターンの集合に対しては「 シフト空間」 という用語を使用しています。 g {\displaystyle g}
参考文献 ^ ab ダグラス・A・リンド; ブライアン・マーカス (1995). シンボリックダイナミクスとコーディング入門 . ケンブリッジ: ケンブリッジ大学出版局. ISBN 978-0-521-55900-3 。 ^ Ceccherini-Silberstein, T.; Coornaert, M. (2010). セルオートマトンと群 Springer Monographs in Mathematics. Springer Monographs in Mathematics. Springer Verlag. doi :10.1007/978-3-642-14034-1. ISBN 978-3-642-14033-4 。 ^ abcd Sobottka, Marcelo (2022年9月). 「シフト空間の分類に関するいくつかの注釈:有限型シフト、ソフィックシフト、有限定義シフト」. ブラジル数学会報 . 新シリーズ. 53 (3): 981– 1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. ISSN 1678-7544. S2CID 254048586. ^ ワイス、ベンジャミン (1973)「有限型とソフィックシステムのサブシフト」、 モナッシュ数学 、 77 (5): 462-474 、 doi :10.1007/bf01295322、 MR 0340556、 S2CID 123440583 ワイスは新語と呼ぶ以外、この単語の起源については何も説明していないが、 MathSciNet の 査読者 RL Adler はヘブライ語起源であると述べている。
さらに読む Ceccherini-Silberstein, T.; Coornaert, M. (2010). セルオートマトンと群 Springer Monographs in Mathematics . Springer Verlag. ISBN 978-3-642-14034-1 。 リンド、ダグラス、マーカス、ブライアン (1995). 『記号力学と符号化入門 』 ケンブリッジ大学出版局 (ケンブリッジ、英国). ISBN 0-521-55900-6 。 ロテール, M. (2002). 「有限語と無限語」. 語に関する代数的組合せ論 . ケンブリッジ大学出版局. ISBN 0-521-81220-8 . 2008年1月29日 閲覧 。 モース、マーストン ; ヘドランド、グスタフ A. (1938). 「記号力学」. アメリカ数学ジャーナル . 60 (4): 815– 866. doi :10.2307/2371264. JSTOR 2371264. Sobottka, M. (2022). 「シフト空間の分類に関するいくつかの注釈:有限型のシフト、ソフィックシフト、そして有限定義シフト」. ブラジル数学会報 . 新シリーズ. 53 (3): 981– 1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. S2CID 254048586.