Subshift av finit typ

Inom matematiken används subshifts av finit typ för att modellera dynamiska system , och är särskilt föremål för studier i symbolisk dynamik och ergodisk teori . De beskriver också uppsättningen av alla möjliga sekvenser som exekveras av en finita tillståndsmaskin . De mest studerade skiftutrymmena är subskiften av finit typ.

Definition

Låt $V$ vara en ändlig uppsättning av $n$ symboler (alfabet). Låt X beteckna mängden $V^{\mathbb {Z} }$ av alla bi-oändliga sekvenser av element i V tillsammans med skiftoperatorn T . Vi ger V den diskreta topologin och X med produkttopologin . Ett symboliskt flöde eller subshift är en sluten T -invariant delmängd Y av X och det associerade språket L _Y är uppsättningen av ändliga delsekvenser av Y .

Låt nu $A$ vara en $n\times n$ angränsande matris med poster i {0,1}. Med hjälp av dessa element konstruerar vi en riktad graf G =( V , E ) med V uppsättningen av hörn och E uppsättningen kanter som innehåller den riktade kanten $x\rightarrow y$ i E om och endast om $A_{x,y}=1$ . Låt Y vara mängden av alla oändliga tillåtna sekvenser av kanter, där det med tillåtlig menas att sekvensen är en gång i grafen, och sekvensen kan vara antingen ensidig eller tvåsidig oändlig. Låt T vara vänster skiftoperator på sådana sekvenser; den spelar rollen som tidsevolutionsoperatören för det dynamiska systemet. Ett subskifte av finit typ definieras då som ett par ( Y , T ) som erhålls på detta sätt. Om sekvensen sträcker sig till oändligheten i endast en riktning kallas den en ensidig subshift av finit typ, och om den är bilateral kallas den för en tvåsidig subshift av finit typ.

Formellt kan man definiera sekvenserna av kanter som

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

Detta är utrymmet för alla sekvenser av symboler så att symbolen p kan följas av symbolen q endast om (p,q):e ^ingången i matrisen A är 1. Rymden för alla bi-oändliga sekvenser definieras analogt:

\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\}.

Skiftoperatorn T mappar en sekvens i det en- eller dubbelsidiga skiftet till en annan genom att flytta alla symboler åt vänster, dvs.

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

Uppenbarligen är denna karta endast inverterbar i fallet med det tvåsidiga skiftet.

En subshift av finit typ kallas transitiv om G är starkt ansluten : det finns en sekvens av kanter från vilken som helst vertex till vilken annan vertex som helst. Det är just transitiva delskiftningar av finit typ som motsvarar dynamiska system med banor som är täta.

Ett viktigt specialfall är den fullständiga n -förskjutningen : den har en graf med en kant som förbinder varje vertex med varannan vertex; det vill säga alla ingångar i närliggande matris är 1. Hela n -förskjutningen motsvarar Bernoulli-schemat utan måttet .

Terminologi

förstås termen förskjutning att hänvisa till hela n -förskjutningen. Ett delskift är då vilket delutrymme som helst av hela skiftet som är skiftinvariant (det vill säga ett delrum som är invariant under skiftoperatorns verkan), icke-tomt och stängt för produkttopologin som definieras nedan. Vissa underskift kan karakteriseras av en övergångsmatris, som ovan; sådana delskiftningar kallas då delskift av finit typ. Ofta kallas subshifts av finit typ helt enkelt för skift av finit typ . Subshifts av finit typ kallas också ibland topologiska Markov-skift .

Exempel

Många kaotiska dynamiska system är isomorfa till subskift av finit typ; exempel inkluderar system med tvärgående homokliniska kopplingar , diffeomorfismer av slutna grenrör med en positiv metrisk entropi , Prouhet -Thue-Morse-systemet, Chacon-systemet (detta är det första systemet som visat sig vara svagt blandat men inte starkt blandat ), Sturmian-system och Toeplitz system.

Generaliseringar

Ett sofic system är en bild av ett subshift av finit typ där olika kanter av övergångsgrafen kan mappas till samma symbol. ^{[ när definieras som? ]} Det kan betraktas som en uppsättning märkningar av vägar genom en automat : ett subskifte av finit typ motsvarar då en automat som är deterministisk . Sådana system motsvarar vanliga språk .

Kontextfria system definieras analogt och genereras av frasstrukturgrammatiker .

Ett förnyelsesystem definieras som uppsättningen av alla oändliga sammanlänkningar av någon fix finit samling av finita ord.

Subshifts av finit typ är identiska med fria (icke-interagerande) endimensionella Potts-modeller ( n -bokstavsgeneraliseringar av Ising-modeller ), med vissa närmaste granne-konfigurationer uteslutna. Interagerande Ising-modeller definieras som underskift tillsammans med en kontinuerlig funktion av konfigurationsutrymmet ^{[ när de definieras som? ]} (kontinuerlig med avseende på produkttopologin, definierad nedan); partitionsfunktionen och Hamiltonian är explicit uttryckbara i termer av denna funktion . ^{[ förtydligande behövs ]}

Subshifts kan kvantiseras på ett visst sätt, vilket leder till idén om den quantum finita automaten .

Topologi

Ett underskift har en naturlig topologi, härledd från produkttopologin på V $\displaystyle V^{\mathbb {Z} }} ,$ där

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

och V ges den diskreta topologin . En grund för topologin för ${\displaystyle V^{\mathbb {Z} }} ,$ som inducerar topologin för subshiften, är familjen cylinderuppsättningar

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

Cylinderuppsättningarna är clopenuppsättningar i $V^{\mathbb {Z} }$ . Varje öppen uppsättning i $V^{\mathbb {Z} }$ är en räknebar förening av cylinderuppsättningar. Varje öppen uppsättning i subshiften är skärningspunkten mellan en öppen uppsättning av $V^{\mathbb {Z} }$ med subshiften. Med avseende på denna topologi är skiftet T en homeomorfism ; det vill säga med avseende på denna topologi är den kontinuerlig med kontinuerlig invers.

Mellanrummet $V^{\mathbb {Z} }$ är homeomorft till en Cantor-uppsättning .

Metrisk

En mängd olika mätvärden kan definieras på ett skiftutrymme. Man kan definiera ett mått på ett skiftutrymme genom att betrakta två punkter som "nära" om de har många initiala symboler gemensamma; detta är den p -adiska metriken . Faktum är att både de ensidiga och tvåsidiga skiftutrymmena är kompakta metriska utrymmen .

Mäta

En subshift av finit typ kan förses med vilken som helst av flera olika mått , vilket leder till ett måttbevarande dynamiskt system . Ett vanligt studieobjekt är Markovmåttet , som är en förlängning av en Markovkedja till skiftets topologi.

En Markov-kedja är ett par ( P ,π) som består av övergångsmatrisen , en $n\times n$ matris $P=(p_{ij})$ för som alla $p_{ij}\geq 0$ och

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

för allt jag . Den stationära sannolikhetsvektorn $\pi =(\pi _{i})$ har alla $\pi _{i}\geq 0,\ summa \pi _{i}=1$ och har

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

.

En Markov-kedja, enligt definitionen ovan, sägs vara kompatibel med skiftningen av finit typ om $p_{ij}=0$ närhelst $A_{ij}=0$ . Markovmåttet för en cylinderuppsättning kan sedan definieras av

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

Kolmogorov –Sinai-entropin med relation till Markovmåttet är

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

Zeta funktion

Artin –Mazur zeta-funktionen definieras som den formella potensserien

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

där Fix( Tn ⁾ är uppsättningen av fixpunkter för det n -faldiga skiftet. Den har en produktformel

\zeta (z)=\prod _{\gamma }(1-z^{|\gamma |})^{-1} \

där γ löper över de slutna banorna. För subshifts av finit typ är zetafunktionen en rationell funktion av z :

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

Se även

Anteckningar

Brin, Michael; Stuck, Garrett (2002). Introduktion till dynamiska system (2:a upplagan). Cambridge University Press . ISBN 0-521-80841-3 .
David Damanik, Strictly Ergodic Subshifts and Associated Operators , (2005)
Pytheas Fogg, N. (2002). Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (red.). Substitutioner i dynamik, aritmetik och kombinatorik . Föreläsningsanteckningar i matematik. Vol. 1794. Berlin: Springer-Verlag . ISBN 3-540-44141-7 . Zbl 1014.11015 .
Natasha Jonoska , Subshifts of Finite Type, Sofic Systems and Graphs , (2000).
Michael S. Keane, Ergodic theory and subshifts of finite type , (1991), som visas som kapitel 2 i Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces , Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). ISBN 0-19-853390-X (Ger en kort redogörelse, med övningar och omfattande referenser.)
Lind, Douglas; Marcus, Brian (1995). En introduktion till symbolisk dynamik och kodning . Cambridge University Press . ISBN 0-521-55124-2 . Zbl 1106.37301 .
Teschl, Gerald (2012). Vanliga differentialekvationer och dynamiska system . Providence : American Mathematical Society . ISBN 978-0-8218-8328-0 .
Xie, Huimin (1996). Grammatisk komplexitet och endimensionella dynamiska system . Vägbeskrivning i Chaos. Vol. 6. World Scientific. ISBN 9810223986 .

Vidare läsning

Williams, Susan G., red. (2004). Symbolic Dynamics and its Applications: American Mathematical Society, Short Course, 4-5 januari 2002, San Diego, Kalifornien . Symposier i tillämpad matematik: AMS korta föreläsningsanteckningar. Vol. 60. American Mathematical Society . ISBN 0-8218-3157-7 . Zbl 1052.37003 .