Простір зсуву

Розглядаються у символьній динаміці та пов'язаних з нею галузях математики. Простори зсуву визначаються множиною нескінченних слів, що представляє розвиток дискретних систем. Насправді, простори зсуву та символьні динамічні системи часто розглядаються як синоніми.

Позначення

Нехай це скінченний алфавіт. Нескінченним (відповідно двобічним нескінченним) словом над називатимемо послідовність $\mathbf {x} =(x_{n})_{n\in M}$, де $M=\mathbb {N}$ (або відповідно $M=\mathbb {Z}$ ) і $x_{n}$ із для довільного цілого п. Оператор зсуву $\sigma$ діє на нескінченному або в два боки нескінченному слові, зсуваючи всі символи на одну позицію ліворуч, тобто

$(\sigma (\mathbf {x} ))(n)=x_{n+1}$ для всіх п.

Надалі покладімо $M=\mathbb {N}$, тобто розглядатимемо однобічно нескінченні слова, хоча всі означення природно узагальнюються і на випадок нескінченних в два боки слів.

Означення

Множину нескінченних слів над називатимемо простором зсуву, якщо вона замкнена щодо природної добуткової топології над $A^{\mathbb {N} }$ і інваріантна щодо зсувів. Таким чином, множина $S\subseteq A^{\mathbb {N} }$ є простором зсуву тоді і лише тоді, якщо

1. для будь-якої збіжної послідовності (поточково) $(\mathbf {x} _{k})_{k\geq 0}$ з елементів S, границя $\lim _{k\to \infty }\mathbf {x} _{k}$ також належить S і
2. $\sigma (S)=S$ .

Простір зсуву іноді позначається як $(S,\sigma )$, щоб підкреслити важливість оператора зсуву.

Деякими авторами використовується термін підзсув, яким позначають довільну множину нескінченних слів, інваріантну щодо зсуву, залишаючи назву "простір зсуву " для тих множини, що є замкненими.

Критерій та софічні підзсуви

S як підмножина $A^{\mathbb {N} }$ є простором зсуву тоді й лише тоді, коли існує множина скінченних заборонених слів F така, що S збігається з множиною всіх нескінченних слів, до яких як підслово не входить жодне з F.

Якщо X є регулярною мовою, відповідний підзсув називається софічним. Зокрема, якщо X є скінченним, то S називається підзсувом скінченного типу.

Приклади

Тривіальним прикладом простору зсуву (скінченного типу) є повний зсув $A^{\mathbb {N} }$ .

Покладімо $A=\{a,b\}$ . Множина всіх нескінченних слів, що містять в собі щонабільше один символ b є софічним підзсувом, нескінченного типу.

Джерела

• Lind, Douglas; Marcus, Brian (1995). An Introduction to Symbolic Dynamics and Coding. Cambridge UK: Cambridge University Press. ISBN 0521559006.
• Lothaire, M. (2002). Finite and Infinite Words. Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0521812208. Процитовано 29 січня 2008.
• Morse, Marston; Hedlund, Gustav A. (1938). Symbolic Dynamics. American Journal of Mathematics. 60 (4): 815—866. doi:10.2307/2371264. JSTOR 2371264.