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

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

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

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

Нехай це скінченний алфавіт. Нескінченним (відповідно двобічним нескінченним) словом над називатимемо послідовність \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), щоб підкреслити важливість оператора зсуву.

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

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

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

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

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

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

Покладімо A=\{a,b\} . Множина всіх нескінченних слів, що містять в собі щонабільше один символ 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.