Простір зсуву
Розглядаються у символьній динаміці та пов'язаних з нею галузях математики. Простори зсуву визначаються множиною нескінченних слів, що представляє розвиток дискретних систем. Насправді, простори зсуву та символьні динамічні системи часто розглядаються як синоніми.
Позначення[ред. | ред. код]
Нехай це скінченний алфавіт. Нескінченним (відповідно двобічним нескінченним) словом над називатимемо послідовність , де (або відповідно ) і із для довільного цілого п. Оператор зсуву діє на нескінченному або в два боки нескінченному слові, зсуваючи всі символи на одну позицію ліворуч, тобто
- для всіх п.
Надалі покладімо , тобто розглядатимемо однобічно нескінченні слова, хоча всі означення природно узагальнюються і на випадок нескінченних в два боки слів.
Означення[ред. | ред. код]
Множину нескінченних слів над називатимемо простором зсуву, якщо вона замкнена щодо природної добуткової топології над і інваріантна щодо зсувів. Таким чином, множина є простором зсуву тоді і лише тоді, якщо
- для будь-якої збіжної послідовності (поточково) з елементів S, границя також належить S і
- .
Простір зсуву іноді позначається як , щоб підкреслити важливість оператора зсуву.
Деякими авторами [1] використовується термін підзсув, яким позначають довільну множину нескінченних слів, інваріантну щодо зсуву, залишаючи назву "простір зсуву " для тих множини, що є замкненими.
Критерій та софічні підзсуви[ред. | ред. код]
S як підмножина є простором зсуву тоді й лише тоді, коли існує множина скінченних заборонених слів F така, що S збігається з множиною всіх нескінченних слів, до яких як підслово не входить жодне з F.
Якщо X є регулярною мовою, відповідний підзсув називається софічним. Зокрема, якщо X є скінченним, то S називається підзсувом скінченного типу.
Приклади[ред. | ред. код]
Тривіальним прикладом простору зсуву (скінченного типу) є повний зсув .
Покладімо . Множина всіх нескінченних слів, що містять в собі щонабільше один символ 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.
Література[ред. | ред. код]
- ↑ Thomsen, K. (2004). On the structure of a sofic shift space (PDF). Transactions of the American Mathematical Society. 356 (9): 3557—3619. doi:10.1090/S0002-9947-04-03437-3. Архів оригіналу (PDF Reprint) за 26 червня 2015. Процитовано 27 січня 2012.
На цю статтю не посилаються інші статті Вікіпедії. Будь ласка розставте посилання відповідно до прийнятих рекомендацій. |