Подсдвиг конечного типа

В математике , subshifts конечного типа используется для моделирования динамических систем , и , в частности , являются объектами изучения в символических динамиках и эргодической теории . Они также описывают набор всех возможных последовательностей, выполняемых конечным автоматом . Наиболее изученными пространствами сдвигов являются подсдвиги конечного типа.

Определение [ править ]

Позвольте быть конечным набором символов (алфавит). Пусть Х обозначает множество всех би-бесконечной последовательности элементов V вместе с оператором сдвига Т . Наделит V с дискретной топологией и X с топологией произведения . Символический поток или subshift является замкнутым Т -инвариантным подмножество Y из X ^[1] и связанный с ним язык L _Y представляет собой множество конечных подпоследовательностей Y . ^[2]${\ displaystyle V}$${\ displaystyle n}$${\ Displaystyle V ^ {\ mathbb {Z}}}$

Пусть теперь будет матрица смежности с элементами в {0,1}. Используя эти элементы, мы строим ориентированный граф G = ( V , E ), где V - множество вершин, а E - множество ребер, содержащих ориентированное ребро в E тогда и только тогда, когда . Пусть Y - множество всех бесконечных допустимых последовательностей ребер, где под допустимыми подразумевается, что последовательность является обходом графа, и последовательность может быть как односторонней, так и двусторонней бесконечной. Пусть T - оператор левого сдвига${\ displaystyle A}$${\ Displaystyle п \ раз п}$ ${\ displaystyle x \ rightarrow y}$${\ displaystyle A_ {x, y} = 1}$на таких последовательностях; он играет роль оператора временной эволюции динамической системы. Subshift конечного типа затем определяется как пара ( Y , Т ) , полученного таким образом. Если последовательность простирается до бесконечности только в одном направлении, это называется односторонним дополнительным сдвигом конечного типа, а если он двусторонний , он называется двусторонним дополнительным сдвигом конечного типа.

Формально можно определить последовательности ребер как

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

Это пространство всех последовательностей символов, так что за символом p может следовать символ q, только если (p, q) ^-й элемент матрицы A равен 1. Пространство всех бибесконечных последовательностей определяется аналогично:

${\displaystyle \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\}.}$

Оператор сдвига T отображает последовательность одностороннего или двустороннего сдвига в другую, сдвигая все символы влево, т. Е.

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

Ясно, что это отображение обратимо только в случае двустороннего сдвига.

Subshift конечного типа называется транзитивным , если G является сильно связным : существует последовательность ребер из какой - либо одной вершины в любую другую вершину. Именно транзитивные поддвиги конечного типа соответствуют динамическим системам с плотными орбитами.

Важным частным случаем является полный n -сдвиг : у него есть граф с ребром, соединяющим каждую вершину с каждой другой вершиной; то есть все элементы матрицы смежности равны 1. Полный n- сдвиг соответствует схеме Бернулли без меры .

Терминология [ править ]

По соглашению, термин « сдвиг» относится к полному n- сдвигу. Subshift тогда любое подпространство полного сдвига , который является инвариантным относительно сдвиг (то есть подпространство, инвариантные относительно действий оператора сдвига), не пусто, и закрыта для топологии продукта , определенной ниже. Некоторые субсдвиги могут быть охарактеризованы матрицей переходов, как указано выше; такие поддвиги тогда называются подсдвигами конечного типа. Часто субсдвиги конечного типа называют просто сдвигами конечного типа . Подсдвиги конечного типа также иногда называют топологическими марковскими сдвигами .

Примеры [ править ]

Многие хаотические динамические системы изоморфны подсмещениям конечного типа; примеры включают в себя систему с поперечными гомоклиническими соединениями , диффеоморфизмы из замкнутых многообразий с положительной метрической энтропией , в системе Пруэ-Туэ- Морзе , в системе Chacon (это первая система , показанной быть слабо перемешивающим , но не с сильным перемешиванием ), штурмова систему и тёплицевой системы . ^[3]

Обобщения [ править ]

Sofic система представляет собой изображение subshift конечного типа , где различные ребра графа переходов может быть сопоставлены с тем же символом. ^{[ когда определяется как? ]} Его можно рассматривать как набор разметок путей через автомат : тогда подсдвиг конечного типа соответствует автомату, который является детерминированным . ^[4] Такие системы соответствуют обычным языкам .

Бесконтекстные системы определяются аналогично и генерируются грамматиками фразовой структуры .

Система обновления определяется как множество всех бесконечных конкатенаций некоторого фиксированного конечного набора конечных слов.

Подсдвиги конечного типа идентичны свободным (невзаимодействующим) одномерным моделям Поттса ( n- буквенные обобщения моделей Изинга ), за исключением некоторых конфигураций ближайшего соседа. Взаимодействующие модели Изинга определяются как субсдвиги вместе с непрерывной функцией конфигурационного пространства ^{[ когда они определены как? ]} (непрерывный относительно топологии продукта, определенной ниже); статсумма и гамильтоново является явно выражается в терминах этой функции. ^{[ требуется разъяснение ]}

Подсдвиги можно квантовать определенным образом, что приводит к идее квантовых конечных автоматов .

Топология [ править ]

Подсдвиг имеет естественную топологию, полученную из топологии продукта на , где${\displaystyle V^{\mathbb {Z} }}$

${\displaystyle 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} \}}$

и V задана дискретная топология . Основой топологии , индуцирующей топологию подсмещения, является семейство цилиндрических множеств${\displaystyle V^{\mathbb {Z} }}$

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

Наборы цилиндра замкнутые множества в . Каждое открытое множество в представляет собой счетное объединение множеств цилиндров. Каждый открытый набор во вспомогательном смещении является пересечением открытого набора с дополнительным смещением. Относительно этой топологии сдвиг T является гомеоморфизмом ; то есть по отношению к этой топологии она непрерывна с непрерывной обратной.${\displaystyle V^{\mathbb {Z} }}$${\displaystyle V^{\mathbb {Z} }}$${\displaystyle V^{\mathbb {Z} }}$

Метрика [ править ]

На сменном пространстве можно определить множество различных показателей. Можно определить метрику на пространстве сдвига, рассматривая две точки как «близкие», если они имеют много общих начальных символов; это p -адическая метрика . Фактически, как одностороннее, так и двустороннее пространство сдвига являются компактными метрическими пространствами .

Измерение [ править ]

Подсдвиг конечного типа может быть снабжен любой из нескольких различных мер , что приводит к сохраняющей меру динамической системе . Обычным объектом изучения является марковская мера , которая является продолжением цепи Маркова до топологии сдвига.

Цепь Маркова представляет собой пару ( Р , π) , состоящий из переходной матрицы , матрицу , для которой все и${\displaystyle n\times n}$${\displaystyle P=(p_{ij})}$${\displaystyle p_{ij}\geq 0}$

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

для всех я . Стационарная вероятность вектор имеет все и имеет${\displaystyle \pi =(\pi _{i})}$${\displaystyle \pi _{i}\geq 0,\sum \pi _{i}=1}$

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

Цепь Маркова, как определено выше, называется совместимой со сдвигом конечного типа, если когда-либо . Тогда марковская мера набора цилиндров может быть определена как${\displaystyle p_{ij}=0}$${\displaystyle A_{ij}=0}$

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

Колмогорова-Sinai энтропия по отношению к мере Маркова

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

Дзета-функция [ править ]

Дзета - функция Артина-Мазура определяется как формальный степенной ряд

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

где Фикс ( Т ^п ) является множество неподвижных точек в п - кратном сдвига. ^[5] У него есть формула продукта

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

где γ пробегает замкнутые орбиты. ^[5] Для subshifts конечного типа, дзета - функция является рациональной функцией от г : ^[6]

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

См. Также [ править ]

• Оператор трансфера
• График Де Брёйна
• Квантовые конечные автоматы
• Аксиома А

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Ноябрь 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Заметки [ править ]

Ссылки [ править ]

• Брин, Майкл; Застрявший, Гарретт (2002). Введение в динамические системы (2-е изд.). Издательство Кембриджского университета . ISBN 0-521-80841-3.
• Дэвид Даманик, Строго эргодические подмены и связанные операторы , (2005)
• Пифей Фогг, Н. (2002). Берте, Валери ; Ференци, Себастьен; Mauduit, Christian; Сигель, А. (ред.). Подстановки в динамике, арифметике и комбинаторике . Конспект лекций по математике. 1794 . Берлин: Springer-Verlag . ISBN 3-540-44141-7. Zbl  1014.11015 .
• Наташа Йоноска , Подсмещения конечного типа, софические системы и графы , (2000).
• Майкл С. Кин, Эргодическая теория и субсдвиги конечного типа , (1991), появившаяся как Глава 2 в Эргодической теории, символической динамике и гиперболических пространствах , Тим Бедфорд, Майкл Кин и серия Кэролайн, ред. Издательство Оксфордского университета, Оксфорд (1991). ISBN 0-19-853390-X (Предоставляет краткое пояснительное введение, с упражнениями и обширными ссылками.) 
• Линд, Дуглас; Маркус, Брайан (1995). Введение в символическую динамику и кодирование . Издательство Кембриджского университета . ISBN 0-521-55124-2. Zbl  1106.37301 .
• Тешл, Джеральд (2012). Обыкновенные дифференциальные уравнения и динамические системы . Провиденс : Американское математическое общество . ISBN 978-0-8218-8328-0.
• Се, Хуэйминь (1996). Грамматическая сложность и одномерные динамические системы . Направления в хаосе. 6 . World Scientific. ISBN 9810223986.

Дальнейшее чтение [ править ]

• Уильямс, Сьюзан Г., изд. (2004). Символическая динамика и ее приложения: Американское математическое общество, краткий курс, 4–5 января 2002 г., Сан-Диего, Калифорния . Материалы симпозиумов по прикладной математике: конспект лекций краткого курса AMS. 60 . Американское математическое общество . ISBN 0-8218-3157-7. Zbl  1052.37003 .