シフトスペース

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

古典的な枠組み^[1]では、シフト空間はの任意の部分集合であり、 は有限集合であり、ティコノフ位相に対して閉じており、平行移動に対して不変である。より一般的には、シフト空間は の閉じた平行移動不変な部分集合として定義することができ、 は任意の空でない集合であり、 は任意のモノイドである。^{[2] [3]}${\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} }$

をモノイ​​ドとし、が与えられたとき、 の積による演算を で表します。をの恒等式 で表します。 離散位相を持つ空でない集合（アルファベット）を考え、を でインデックス付けされた上のすべてのパターンの集合 と定義します。および部分集合について、のインデックスへの の制限を で表します。 ${\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|}}$

が与えられたとき、上のgシフト写像は と表され、次のように定義される。 ${\displaystyle g\in \mathbb {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} }}$。

アルファベット上のシフト空間は、 の位相で閉じられ、変換で不変である、つまりすべての に対して である集合です。^{[注 1]}シフト空間で、シリンダー を基本開集合として持つからの誘導位相を考えます。 ${\displaystyle A}$${\displaystyle \Lambda \subset A^{\mathbb {G} }}$${\displaystyle A^{\mathbb {G}}}$${\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda }$${\displaystyle g\in \mathbb {G} }$${\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} }$

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

ここで、andは空語を表し、 ${\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}$

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

アルファベットが有限の場合、となる禁制パターンの有限集合を取ることができるときシフト空間は有限型のシフトであり、はスライディングブロックコード^[1]の下で有限型のシフトの像であるとき（つまり、すべての -シフト写像 に対して連続かつ不変な写像）、 はソフィックシフトである。が有限で または通常の加算で である場合、 が正規言語である場合に限り、シフトはソフィックシフトである。 ${\displaystyle A}$${\displaystyle \Lambda }$${\displaystyle F}$${\displaystyle \Lambda =X_{F}}$${\displaystyle \Lambda }$${\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{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},}$

は有限であり、である。^[3]この無限アルファベットの文脈では、ソフィックシフトは、特定のクラスのスライディングブロックコードの下での有限タイプのシフトの像として定義される。^[3]が有限である場合、の有限性とスライディングブロックコードの追加条件の両方が自明に満たされる。 ${\displaystyle \Lambda =X_{F}}$${\displaystyle M_{F}}$${\displaystyle A}$

シフト空間は、記号的動的システムが通常定義される位相空間です。

シフト空間と-シフトマップが与えられると、そのペアは位相的な動的システムであることがわかります。 ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$${\displaystyle g}$${\displaystyle \sigma ^{g}:\Lambda \to \Lambda }$${\displaystyle (\Lambda ,\sigma ^{g})}$

2つのシフト空間 および が位相共役（または単に共役）であるとは、各-シフト写像に対して位相力学系およびが位相共役 となる場合、つまり となる 連続写像が存在する場合を言う。このような写像は、が一様連続である場合は常に、一般化スライディングブロック符号または単にスライディングブロック符号として知られている。 ^[3]${\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 }$

から への任意の連続写像はそれ自体で位相的力学系 を定義しますが、記号力学では、すべての - シフト写像と可換な連続写像、つまり一般化されたスライディング ブロック コードである写像のみを考慮するのが一般的です。この力学系は「一般化セルラー オートマトン」 (または が一様連続である場合は単にセルラー オートマトン) として知られています。 ${\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} }}$

とする。最大で 1 つのb を含むA上のすべての無限ワードの集合は、有限型ではなく、ソフィック サブシフトです。bが素数の長さのブロックを形成するA上のすべての無限ワードの集合は、ソフィックではありません (これは、ポンピング レンマを使用して示すことができます)。 ${\displaystyle A=\{a,b\}}$

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

2 つの文字の文字列の双無限空間は、一般にベイカー写像として知られており、むしろベイカー写像と準同型です。 ${\displaystyle \{0,1\}^{\mathbb {Z} }}$

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

• Ceccherini-Silberstein, T.; Coornaert, M. (2010).セルオートマトンと群 Springer Monographs in Mathematics . Springer Verlag. ISBN 978-3-642-14034-1。
• リンド、ダグラス、マ​​ーカス、ブライアン (1995)。シンボリックダイナミクスとコーディング入門。ケンブリッジ、イギリス: ケンブリッジ大学出版局。ISBN 0-521-55900-6。
• Lothaire, 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  。