有限型のサブシフト

数学において、有限型部分シフトとは、有限個の禁止語によって定義されるシフト空間のことである。これらは力学系のモデル化に用いられ、特に記号力学やエルゴード理論において研究対象となっている。また、有限状態機械によって実行されるすべての可能なシーケンスの集合を表す。最も広く研究されているシフト空間は、有限型部分シフトである。

有限型の（片側）シフトの一例として、文字から構成される、片端のみが無限であるすべてのシーケンスの集合が挙げられる。${\displaystyle A,B}$、 のように${\displaystyle AAA\cdots ,ABAB\cdots ,\dots }$これはフルシフトと呼ばれ、次のように表されます。${\displaystyle \{A,B\}^{\mathbb {N} }}$。

その言葉を禁止することによって${\displaystyle BB}$有限型のシフトを定義する${\displaystyle \Sigma =\{(x_{0},x_{1},x_{2},\ldots )\mid x_{i}x_{i+1}\neq BB\}}$ゴールデンシフトと呼ばれる、長さの法的単語の数からそう呼ばれる${\displaystyle n}$はフィボナッチ数列です。有限型の両側シフトはこれに似ていますが、両端が無限となる数列で構成されます。

部分シフトは、文字上の有向グラフによって定義できます。例えば、グラフ${\displaystyle A\to B\to C\to A}$これは、連続する文字間の遷移がグラフで許可されているものだけであるシーケンスで構成されます。この例では、サブシフトは3つの片側シーケンスのみで構成されます。${\displaystyle ABCABC\cdots ,BCABCA\cdots ,CABCAB\cdots }$同様に、このグラフで示される両側サブシフトは、3つの両側シーケンスのみで構成されています。

同じ文字上の他の有向グラフは、別のサブシフトを生成します。たとえば、別の矢印を追加すると${\displaystyle A\to C}$このグラフは、3つのシーケンスを含む代わりに、非可算無限個のシーケンスを含む部分シフトを生成する。文字の局所的な再符号化を除けば、有限型のあらゆる部分シフトは、このような有向グラフで記述できる。

させて${\displaystyle {\mathcal {A}}}$有限集合である${\displaystyle n}$記号（アルファベット）。${\displaystyle X}$集合を表す${\displaystyle {\mathcal {A}}^{\mathbb {Z} }}$要素のすべての双無限列の${\displaystyle {\mathcal {A}}}$シフトオペレーターと共に${\displaystyle T}$私たちは寄付します${\displaystyle {\mathcal {A}}}$離散トポロジーと${\displaystyle X}$積トポロジーを持つ。シンボリックフローまたはサブシフトは閉じた${\displaystyle T}$-不変部分集合${\displaystyle Y}$の${\displaystyle X}$^{[ 1 ]}および関連言語${\displaystyle {\mathcal {L}}_{Y}}$は、の要素の有限部分語の集合である。${\displaystyle Y}$[ ^{2 ]​}

させて${\displaystyle F}$アルファベットの有限個の単語の集合である${\displaystyle {\mathcal {A}}}$これらは禁止語と呼ばれます。関連する有限型のサブシフトは空間として定義されます。

$${\displaystyle \Sigma _{F}=\{(x_{0},x_{1},x_{2},\ldots )\mid \forall i,k\geq 0,x_{i}x_{i+1}\cdots x_{i+k}\notin F\}}$$

禁止語のセットを回避するシーケンス${\displaystyle F}$。

上記のように、数列が一方向のみに無限に続く場合、それは有限型の片側部分シフトと呼ばれ、両側に続く場合は、有限型の両側部分シフトと呼ばれます。

シフトオペレーター${\displaystyle T}$片側または両側シフトのシーケンスを、すべてのシンボルを左にシフトすることによって別のシーケンスにマッピングします。

$${\displaystyle (T(x))_{i}=x_{i+1}.}$$

明らかに、このマップは両側シフトの場合にのみ可逆である。

特に有用なサブクラスは、エッジシフトによって与えられます。Aを{ 0 , 1}のエントリを持つn × n隣接行列とします。これらの要素を使用して、頂点の集合Vと、 A _x , y = 1の場合に限りEに有向エッジx → yを含むエッジの集合である有向グラフG = ( V _{, E} )を構築します。Yをすべての無限許容エッジ列の集合とします。ここで、許容とは、列がグラフのウォークであることを意味し、列は片側または両側の無限のいずれかです。T をそのような列に対する左シフト演算子とします。これは、動的システムの時間発展演算子の役割を果たします。エッジシフトは、このようにして得られるペア( Y , T )として定義されます。

形式的には、エッジのシーケンスを次のように定義することができる。

${\displaystyle \Sigma _{A}^{+}=\left\{(x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {N} \right\}.}$

これは、記号pの後に記号qが続くことができるのは、行列Aの( p , q )番目の要素が 1 である場合に限る、すべての記号列の空間です。すべての双無限列の空間は、同様に定義されます。

${\displaystyle \Sigma _{A}=\left\{(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{j}\in V,A_{x_{j}x_{j+1}}=1,j\in \mathbb {Z} \right\}.}$

エッジシフトは、禁止語の集合が2文字の単語のみで構成される有限型のサブシフトのサブセットです。一方、有限型のすべてのサブシフトは、局所的な再符号化を介してエッジシフトと位相的に共役であることが示せます。^{[ 3 ]}

辺シフトは、 Gが強連結である場合、すなわち任意の頂点から他の任意の頂点への辺の列が存在する場合に、推移的であると呼ばれる。稠密軌道を持つ有限型の部分シフトは、まさに推移的な辺シフトと共役な部分シフトである。

重要な特殊ケースは、完全なnシフトです。これは、すべての頂点を他のすべての頂点に接続するエッジを持つグラフを持ちます。つまり、隣接行列のすべてのエントリは 1 です。完全なnシフトは、測度のないベルヌーイ スキームに対応します。

慣例として、シフトという用語は完全なnシフトを指すものと理解されています。部分シフトとは、完全なシフトの任意の部分空間で、シフト不変（つまり、シフト演算子の作用の下で不変な部分空間）、空でない、かつ、以下に定義される積位相に対して閉じているものです。一部の部分シフトは、上記のように遷移行列によって特徴付けられます。このような部分シフトは、有限型部分シフトと呼ばれます。多くの場合、有限型部分シフトは単に有限型シフトと呼ばれます。有限型部分シフトは、位相的マルコフシフトと呼ばれることもあります。

多くのカオス的な力学系は有限型の部分シフトと同型である。例としては、横断的なホモクリニック接続を持つシステム、正の計量エントロピーを持つ閉多様体の微分同相写像、区間の区分的線形マルコフ写像などが挙げられる。

部分シフトは、上の積位相から派生した自然な位相を持つ。${\displaystyle V^{\mathbb {Z} },}$場所​

$${\displaystyle V^{\mathbb {Z} }=\prod _{n\in \mathbb {Z} }V=\{x=(\ldots ,x_{-1},x_{0},x_{1},\ldots ):x_{k}\in V\;\forall k\in \mathbb {Z} \}}$$

Vには離散位相が与えられます。 の位相の基底は です。${\displaystyle V^{\mathbb {Z} },}$サブシフトのトポロジーを誘導するのは、シリンダー集合の族である。

${\displaystyle C_{t}[a_{0},\ldots ,a_{s}]=\{x\in V^{\mathbb {Z} }:x_{t}=a_{0},\ldots ,x_{t+s}=a_{s}\}}$

シリンダー集合は、${\displaystyle V^{\mathbb {Z} }.}$⁠すべてのオープンセットは⁠${\displaystyle V^{\mathbb {Z} }}$はシリンダー集合の可算和集合です。部分シフト内のすべての開集合は、 の開集合の共通部分です。${\displaystyle V^{\mathbb {Z} }}$サブシフト付き。この位相に関して、シフトTは同相写像です。つまり、この位相に関して、連続かつ連続な逆写像を持ちます。

空間​${\displaystyle V^{\mathbb {Z} }}$はカントール集合と同相である。

シフト空間上には、さまざまな距離尺度を定義できます。2つの点が共通の初期記号を多く持つ場合、それらの点が「近い」と考えることで、シフト空間上の距離尺度を定義できます。これはp進距離です。実際、片側シフト空間と両側シフト空間はどちらもコンパクトな距離空間です。

有限型の部分シフトには、いくつかの異なる測度のいずれかを付与することができ、それによって測度保存力学系が得られる。よく研究される対象はマルコフ測度であり、これはマルコフ連鎖をシフトの位相に拡張したものである。

マルコフ連鎖は、遷移行列、n × n行列P = ( p _ij ) （すべてのp _ij ≥ 0および

${\displaystyle \sum _{j=1}^{n}p_{ij}=1}$

すべてのiに対して。定常確率ベクトルπ = ( π _i )はすべてのπ _i ≥ 0を持ちます。${\textstyle \sum \pi _{i}=1}$そして

${\displaystyle \sum _{i=1}^{n}\pi _{i}p_{ij}=\pi _{j}.}$

上記で定義したマルコフ連鎖は、A ij = 0 のとき p ij = 0 である場合に有限型のシフトと互換​​性があると言われる。_{シリンダー}集合のマルコフ_測度は次のように定義できる。

${\displaystyle \mu (C_{t}[a_{0},\ldots ,a_{s}])=\pi _{a_{0}}p_{a_{0},a_{1}}\cdots p_{a_{s-1},a_{s}}}$

マルコフ測度に関連するコルモゴロフ・シナイエントロピーは

${\displaystyle s_{\mu }=-\sum _{i=1}^{n}\pi _{i}\sum _{j=1}^{n}p_{ij}\log p_{ij}}$

マルコフ尺度と非マルコフ尺度

上記のように、マルコフ遷移行列と状態に対する不変分布が与えられれば、部分シフトに確率測度を課すことができます。例えば、左側に示された状態に対するマルコフ連鎖を考えてみましょう。${\displaystyle A,B_{1},B_{2}}$不変分布${\displaystyle \pi =(2/7,4/7,1/7)}$. もし私たちが次の区別を「忘れる」ならば${\displaystyle B_{1},B_{2}}$このサブシフトを投影すると${\displaystyle A,B_{1},B_{2}}$サブシフトに${\displaystyle A,B}$また、この投影は確率測度をサブシフト上の確率測度に投影します。${\displaystyle A,B}$。

興味深いのは、サブシフトの確率測度が${\displaystyle A,B}$はマルコフ連鎖によって生成されません${\displaystyle A,B}$複数の順序さえありません。直感的には、これは、長いシーケンスを観察すると、${\displaystyle B^{n}}$そうすれば、${\displaystyle Pr(A|B^{n})\to {\frac {2}{3}}}$つまり、システムの観測可能な部分は、無限に過去の何かに影響を受ける可能性があるということである。^{[ 4 ] [ 5 ]}

逆に、6 個のシンボル上の部分シフトが存在し、それが 2 個のシンボル上の部分シフトに射影され、小さい方の部分シフト上の任意のマルコフ測度は、どの次数においてもマルコフではない逆像測度を持つ（例 2.6 ^{[ 5 ]}）。

アルティン・マズールのゼータ関数は、形式的べき級数として定義される。

${\displaystyle \zeta (z)=\exp \left(\sum _{n=1}^{\infty }{\Bigl |}{\textrm {Fix}}(T^{n}){\Bigr |}{\frac {z^{n}}{n}}\right),}$

ここで、Fix( Tn ⁾はn重シフトの不動点の集合である。 ^{[ 6 ]} これは積公式を持つ。

${\displaystyle \zeta (z)=\prod _{\gamma }\left(1-z^{|\gamma |}\right)^{-1}\ }$

ここでγは閉軌道上を走ります。^{[ 6 ]} 有限型のサブシフトの場合、ゼータ関数はzの有理関数です。^{[ 7 ]}

${\displaystyle \zeta (z)=(\det(I-zA))^{-1}\ .}$

ソフィックシフトは、遷移グラフの異なるエッジが同じシンボルにマッピングされる有限型のサブシフトのイメージです。たとえば、隠れマルコフ連鎖からの出力だけを観察すると、出力はソフィックシステムのように見えます。^{[ 4 ]}これは、オートマトンを通るパスのラベル付けの集合と見なすことができます。有限型のサブシフトは、決定論的なオートマトンに対応します。^{[ 8 ]}このようなシステムは正規言語に対応します。

文脈自由システムは同様に定義され、句構造文法によって生成される。

再生システムは、ある固定された有限個の有限語の集合のすべての無限連結の集合として定義される。

有限型のサブシフトは、特定の最近接配置を除けば、自由（非相互作用）一次元ポッツモデル（イジングモデルのn文字一般化）と同一である。相互作用するイジングモデルは、サブシフトと配置空間の連続関数（以下で定義する積トポロジーに関して連続）として定義される。分配関数とハミルトニアンは、この関数を用いて明示的に表現できる。

部分シフトはある特定の方法で量子化することができ、それが量子有限オートマトンの概念につながる。

• シフトスペース
• 転送オペレーター
• デ・ブルイングラフ
• 量子有限オートマトン
• 公理A
• グラフのファイブレーション

• ブリン、マイケル；スタック、ギャレット（2002）。力学系入門（第2 版）。ケンブリッジ大学出版局。ISBN 0-521-80841-3。
• デイビッド・ダマニク著『厳密にエルゴード的な部分シフトと関連演算子』（2005年）
• ピテアス・フォッグ、N. (2002)。Berthé, ヴァレリー;フェレンチ、セバスチャン。モーデュイ、クリスチャン。シーゲル、A. (編)。力学、算術、組み合わせ論における置換。数学の講義ノート。 Vol.  1794年。ベルリン：シュプリンガー・フェルラーク。ISBN 3-540-44141-7. Zbl 1014.11015 . 
• ナターシャ・ジョノスカ、「有限型の部分シフト」、ソフィックシステムとグラフ、（2000）。
• マイケル・S・キーン著「エルゴード理論と有限型部分シフト」（1991年）、ティム・ベッドフォード、マイケル・キーン、キャロライン・シリーズ編『エルゴード理論、記号力学、双曲空間』第2章として収録。オックスフォード大学出版局、オックスフォード（1991年）。ISBN 0-19-853390-X（簡潔な解説、練習問題、豊富な参考文献を掲載しています。）
• リンド、ダグラス、マ​​ーカス、ブライアン（1995）。記号力学と符号化入門。ケンブリッジ大学出版局。ISBN 0-521-55124-2. Zbl 1106.37301 . 
• テシュル、ジェラルド（2012）。常微分方程式と力学系。プロビデンス：アメリカ数学会。ISBN 978-0-8218-8328-0。
• 謝慧民 (1996).文法複雑性と一次元力学系. カオスの方向性. 第 6巻. World Scientific. ISBN 9810223986。

• ウィリアムズ、スーザン・G. 編 (2004).記号力学とその応用：アメリカ数学会短期講座、2002年1月4-5日、カリフォルニア州サンディエゴ。応用数学シンポジウム議事録：AMS短期講座講義ノート。第60巻。アメリカ 数学会。ISBN 0-8218-3157-7. Zbl 1052.37003 .