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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Позначення[ред.ред. код]

Нехай це скінченний алфавіт. Нескінченним (відповідно двобічним нескінченним) словом над називатимемо послідовність , де (або відповідно ) і із для довільного цілого п. Оператор зсуву діє на нескінченному або в два боки нескінченному слові, зсуваючи всі символи на одну позицію ліворуч, тобто

для всіх п.

Надалі покладімо , тобто розглядатимемо однобічно нескінченні слова, хоча всі означення природно узагальнюються і на випадок нескінченних в два боки слів.

Означення[ред.ред. код]

Множину нескінченних слів над називатимемо простором зсуву, якщо вона замкнена щодо природньої добуткової топології над і інваріантна щодо зсувів. Таким чином, множиина є простором звсуву тоді і лише тоді, якщо

  1. для будь-якої збіжної послідовності (поточково) з елементів S, границя також належить S і
  2. .

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

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

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

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

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

Приклади[ред.ред. код]

Тривіальним прикладом простору зсуву (скінченного типу) є повний зсув .

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

Джерела[ред.ред. код]

Література[ред.ред. код]

  1. Thomsen, K. (2004). On the structure of a sofic shift space (PDF Reprint). Transactions of the American Mathematical Society 356 (9). с. 3557–3619. doi:10.1090/S0002-9947-04-03437-3. Процитовано 2012-01-27.