Сдвиг пространства

Набор бесконечных слов

В символической динамике и смежных разделах математики сдвиговое пространство или подсдвиг — это набор бесконечных слов , которые представляют эволюцию дискретной системы . Фактически, сдвиговые пространства и символические динамические системы часто считаются синонимами . Наиболее широко изученными сдвиговыми пространствами являются подсдвиги конечного типа и софические сдвиги.

В классической структуре ^[1] сдвиговое пространство — это любое подмножество , где — конечное множество, замкнутое для топологии Тихонова и инвариантное относительно сдвигов. В более общем смысле сдвиговое пространство можно определить как замкнутое и инвариантное относительно сдвигов подмножество , где — любое непустое множество, а — любой моноид . ^{[2] [3]} ${\displaystyle \Lambda }$ ${\displaystyle A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}}$ ${\displaystyle A}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$

Определение

Пусть будет моноидом , и задано , обозначим операцию с произведением . Пусть обозначим единицу . Рассмотрим непустое множество (алфавит) с дискретной топологией и определим как множество всех шаблонов над , индексированных . Для и подмножества обозначим ограничение на индексы как . ${\displaystyle \mathbb {G} }$ ${\displaystyle g,h\in \mathbb {G} }$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle gh}$ ${\displaystyle \mathbf {1} _{\mathbb {G} }}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle A}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }}$ ${\displaystyle N\subset \mathbb {G} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle N}$ ${\displaystyle \mathbf {x} _{N}:=(x_{i})_{i\in N}}$

На мы рассматриваем продискретную топологию, которая делает топологическое пространство Хаусдорфовым и полностью несвязным. В случае конечности следует, что компактно. Однако, если не конечно, то не является даже локально компактным. ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A}$ ${\displaystyle A^{\mathbb {G} }}$

Эта топология будет метризуемой тогда и только тогда, когда является счетной, и, в любом случае, база этой топологии состоит из набора открытых/замкнутых множеств (называемых цилиндрами), определяемых следующим образом: задан конечный набор индексов , и для каждого , пусть . Цилиндр, заданный и является множеством ${\displaystyle \mathbb {G} }$ ${\displaystyle D\subset \mathbb {G} }$ ${\displaystyle i\in D}$ ${\displaystyle a_{i}\in A}$ ${\displaystyle D}$ ${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$

 ${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.}$

При , мы обозначаем цилиндр, фиксирующий символ на записи, индексированной просто как . ${\displaystyle D=\{g\}}$ ${\displaystyle b}$ ${\displaystyle g}$ ${\displaystyle [b]_{g}}$

Другими словами, цилиндр — это множество всех множеств всех бесконечных узоров , содержащих конечный узор . ${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$

При условии , что отображение g -сдвига обозначается и определяется как ${\displaystyle g\in \mathbb {G} }$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle \sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }}$

 ${\displaystyle \sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }}$.

Пространство сдвига над алфавитом — это множество , замкнутое относительно топологии и инвариантное относительно сдвигов, т. е. для всех . ^{[примечание 1]} Мы рассматриваем в пространстве сдвига индуцированную топологию из , которая имеет в качестве базовых открытых множеств цилиндры . ${\displaystyle A}$ ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda }$ ${\displaystyle g\in \mathbb {G} }$ ${\displaystyle \Lambda }$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda }$

Для каждого определите , и . Эквивалентный способ определить сдвиговое пространство — взять набор запрещенных шаблонов и определить сдвиговое пространство как набор ${\displaystyle k\in \mathbb {N} ^{*}}$ ${\displaystyle {\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}}$ ${\displaystyle {\mathcal {N}}_{A^{\mathbb {G} }}^{f}:=\bigcup _{k\in \mathbb {N} }{\mathcal {N}}_{k}=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }A^{N}}$ ${\displaystyle F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}}$

 ${\displaystyle X_{F}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ \forall N\subset \mathbb {G} ,\forall g\in \mathbb {G} ,\ \left(\sigma ^{g}(\mathbf {x} )\right)_{N}=\mathbf {x} _{gN}\notin F\}.}$

Интуитивно, пространство сдвига — это множество всех бесконечных шаблонов, которые не содержат ни одного запрещенного конечного шаблона . ${\displaystyle X_{F}}$ ${\displaystyle F}$

Язык сдвига пространства

При наличии пространства сдвига и конечного набора индексов пусть , где обозначает пустое слово, а для пусть будет набором всех конечных конфигураций , которые появляются в некоторой последовательности , т.е. ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle N\subset \mathbb {G} }$ ${\displaystyle W_{\emptyset }(\Lambda ):=\{\epsilon \}}$ ${\displaystyle \epsilon }$ ${\displaystyle N\neq \emptyset }$ ${\displaystyle W_{N}(\Lambda )\subset A^{N}}$ ${\displaystyle A^{N}}$ ${\displaystyle \Lambda }$

 ${\displaystyle W_{N}(\Lambda ):=\{(w_{i})_{i\in N}\in A^{N}:\ \exists \ \mathbf {x} \in \Lambda {\text{ s.t. }}x_{i}=w_{i}\ \forall i\in N\}.}$

Обратите внимание, что, поскольку является сдвиговым пространством, если является переносом , т. е. для некоторого , то тогда и только тогда, когда существует такой, что если . Другими словами, и содержат те же конфигурации по модулю переноса. Мы будем называть множество ${\displaystyle \Lambda }$ ${\displaystyle M\subset \mathbb {G} }$ ${\displaystyle N\subset \mathbb {G} }$ ${\displaystyle M=gN}$ ${\displaystyle g\in \mathbb {G} }$ ${\displaystyle (w_{j})_{j\in M}\in W_{M}(\Lambda )}$ ${\displaystyle (v_{i})_{i\in N}\in W_{N}(\Lambda )}$ ${\displaystyle w_{j}=v_{i}}$ ${\displaystyle j=gi}$ ${\displaystyle W_{M}(\Lambda )}$ ${\displaystyle W_{N}(\Lambda )}$

 ${\displaystyle W(\Lambda ):=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }W_{N}(\Lambda )}$

язык . В общем контексте, изложенном здесь, язык сдвигового пространства не имеет того же значения, что и в формальной теории языка , но в классической структуре, которая рассматривает алфавит как конечный и являющийся или с обычным добавлением, язык сдвигового пространства является формальным языком . ${\displaystyle \Lambda }$ ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$

Классическая структура

Классическая структура для сдвиговых пространств состоит из рассмотрения алфавита как конечного и как множества неотрицательных целых чисел ( ) с обычным сложением, или множества всех целых чисел ( ) с обычным сложением. В обоих случаях элемент тождества соответствует числу 0. Кроме того, когда , поскольку все могут быть сгенерированы из числа 1, достаточно рассмотреть уникальную карту сдвига, заданную для всех . С другой стороны, для случая , поскольку все могут быть сгенерированы из чисел {-1, 1}, достаточно рассмотреть две карты сдвига, заданные для всех по и по . ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbf {1} _{\mathbb {G} }}$ ${\displaystyle \mathbb {G} =\mathbb {N} }$ ${\displaystyle \mathbb {N} \setminus \{0\}}$ ${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$ ${\displaystyle n}$ ${\displaystyle \mathbb {G} =\mathbb {Z} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle n}$ ${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$ ${\displaystyle \sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}}$

Кроме того, всякий раз, когда есть или с обычным сложением (независимо от мощности ), в силу его алгебраической структуры достаточно рассматривать только цилиндры в форме ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle A}$

 ${\displaystyle [a_{0}a_{1}...a_{n}]:=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.}$

Более того, язык пространства сдвига будет задан как ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$

 ${\displaystyle W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),}$

где и обозначает пустое слово, и ${\displaystyle W_{0}:=\{\epsilon \}}$ ${\displaystyle \epsilon }$

 ${\displaystyle W_{n}(\Lambda ):=\{((a_{i})_{i=0,..n}\in A^{n}:\ \exists \mathbf {x} \in \Lambda \ s.t.\ x_{i}=a_{i}\ \forall i=0,...,n\}.}$

Точно так же для частного случая следует, что для определения сдвигового пространства нам не нужно указывать индекс , на котором определены запрещенные слова , то есть мы можем просто рассмотреть и затем ${\displaystyle \mathbb {G} =\mathbb {Z} }$ ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle F}$ ${\displaystyle F\subset \bigcup _{n\geq 1}A^{n}}$

 ${\displaystyle X_{F}=\{\mathbb {x} \in A^{\mathbb {Z} }:\ \forall i\in \mathbb {Z} ,\ \forall k\geq 0,\ (x_{i}...x_{i+k})\notin F\}.}$

Однако, если , если мы определим сдвиговое пространство , как указано выше, не указывая индекс, где слова запрещены, то мы просто захватим сдвиговые пространства, которые инвариантны относительно карты сдвига, то есть такие, что . Фактически, чтобы определить сдвиговое пространство таким образом, что необходимо будет указать, с какого индекса слова запрещены. ${\displaystyle \mathbb {G} =\mathbb {N} }$ ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle \sigma (X_{F})=X_{F}}$ ${\displaystyle X_{F}\subset A^{\mathbb {N} }}$ ${\displaystyle \sigma (X_{F})\subsetneq X_{F}}$ ${\displaystyle F}$

В частности, в классических рамках конечности и ) или с обычным добавлением следует, что конечно тогда и только тогда, когда конечно, что приводит к классическому определению сдвига конечного типа как тех пространств сдвига, что для некоторого конечного . ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle M_{F}}$ ${\displaystyle F}$ ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle F}$

Некоторые типы смен

Среди нескольких типов пространств сдвига наиболее широко изучены сдвиги конечного типа и софические сдвиги.

В случае, когда алфавит конечен, пространство сдвига является сдвигом конечного типа , если мы можем взять конечный набор запрещенных шаблонов, таких что , и является софическим сдвигом , если он является образом сдвига конечного типа при скользящем блочном коде ^[1] (то есть отображением, которое является непрерывным и инвариантным для всех отображений -сдвига ). Если является конечным и является или с обычным сложением, то сдвиг является софическим сдвигом тогда и только тогда, когда является регулярным языком . ${\displaystyle A}$ ${\displaystyle \Lambda }$ ${\displaystyle F}$ ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle \Lambda }$ ${\displaystyle \Phi }$ ${\displaystyle g}$ ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \Lambda }$ ${\displaystyle W(\Lambda )}$

Название «софический» было придумано Вайсом (1973) на основе еврейского слова סופי, означающего «конечный», для обозначения того факта, что это обобщение свойства конечности. ^[4]

Когда бесконечно, можно определить сдвиги конечного типа как сдвиговые пространства , для которых можно взять набор запрещенных слов такой, что ${\displaystyle A}$ ${\displaystyle \Lambda }$ ${\displaystyle F}$

 ${\displaystyle M_{F}:=\{g\in \mathbb {G} :\ \exists N\subset \mathbb {G} {\text{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},}$

конечен и . ^[3] В этом контексте бесконечного алфавита софический сдвиг будет определен как образ сдвига конечного типа при определенном классе скользящих блочных кодов. ^[3] И конечность, и дополнительные условия скользящих блочных кодов тривиально выполняются, когда конечны. ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle M_{F}}$ ${\displaystyle A}$

Топологические динамические системы на сдвиговых пространствах

Пространства сдвига — это топологические пространства , на которых обычно определяются символические динамические системы .

Учитывая пространство сдвига и отображение -сдвига, следует, что пара представляет собой топологическую динамическую систему . ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle g}$ ${\displaystyle \sigma ^{g}:\Lambda \to \Lambda }$ ${\displaystyle (\Lambda ,\sigma ^{g})}$

Два пространства сдвига и называются топологически сопряженными (или просто сопряженными), если для каждого отображения сдвига следует, что топологические динамические системы и являются топологически сопряженными , то есть если существует непрерывное отображение такое, что . Такие отображения известны как обобщенные скользящие блочные коды или просто как скользящие блочные коды, когда является равномерно непрерывным. ^[3] ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle \Gamma \subset B^{\mathbb {G} }}$ ${\displaystyle g}$ ${\displaystyle (\Lambda ,\sigma ^{g})}$ ${\displaystyle (\Gamma ,\sigma ^{g})}$ ${\displaystyle \Phi :\Lambda \to \Gamma }$ ${\displaystyle \Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi }$ ${\displaystyle \Phi }$

Хотя любое непрерывное отображение из в себя будет определять топологическую динамическую систему , в символической динамике обычно рассматриваются только непрерывные отображения , которые коммутируют со всеми -сдвиговыми отображениями, т.е. отображения, которые являются обобщенными скользящими блочными кодами. Динамическая система известна как « обобщенный клеточный автомат» (или просто как клеточный автомат, когда является равномерно непрерывным). ${\displaystyle \Phi }$ ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle (\Lambda ,\Phi )}$ ${\displaystyle \Phi :\Lambda \to \Lambda }$ ${\displaystyle g}$ ${\displaystyle (\Lambda ,\Phi )}$ ${\displaystyle \Phi }$

Примеры

Первым тривиальным примером пространства сдвига (конечного типа) является полный сдвиг . ${\displaystyle A^{\mathbb {N} }}$

Пусть . Множество всех бесконечных слов над A, содержащих не более одного b, является софическим подсдвигом, не конечного типа. Множество всех бесконечных слов над A , чьи b образуют блоки простой длины, не является софическим (это можно показать с помощью леммы о накачке ). ${\displaystyle A=\{a,b\}}$

Пространство бесконечных струн в двух буквах называется процессом Бернулли . Оно изоморфно множеству Кантора . ${\displaystyle \{0,1\}^{\mathbb {N} }}$

Би-бесконечное пространство строк из двух букв обычно известно как отображение Бейкера или, скорее, гомоморфно отображению Бейкера. ${\displaystyle \{0,1\}^{\mathbb {Z} }}$

Смотрите также

• Карта палаток
• Карта битового сдвига
• Код Грея

Сноски

1. Обычно для обозначения пространства сдвига используют просто выражение сдвиг или подсдвиг . Однако некоторые авторы используют термины сдвиг и подсдвиг для множеств бесконечных шаблонов, которые просто инвариантны относительно отображений -сдвига, и резервируют термин пространство сдвига для тех, которые также замкнуты для продискретной топологии. ${\displaystyle g}$

Ссылки

1. Линд, Дуглас А.; Маркус, Брайан (1995). Введение в символическую динамику и кодирование . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-55900-3.
2. Чеккерини-Зильберштейн, Т.; Коорнарт, М. (2010). Клеточные автоматы и группы Springer Monographs in Mathematics. Springer Monographs in Mathematics. Springer Verlag. doi :10.1007/978-3-642-14034-1. ISBN 978-3-642-14033-4.
3. Sobottka, Marcelo (сентябрь 2022 г.). «Некоторые заметки о классификации пространств сдвига: сдвиги конечного типа; софические сдвиги; и конечно определенные сдвиги». Бюллетень Бразильского математического общества . Новая серия. 53 (3): 981–1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. ISSN  1678-7544. S2CID  254048586.
4. Вайс, Бенджамин (1973), «Подсдвиги конечного типа и софические системы», Monatsh. Math. , 77 (5): 462–474, doi :10.1007/bf01295322, MR  0340556, S2CID  123440583. Вайс не описывает происхождение слова, а лишь называет его неологизмом; однако рецензент MathSciNet Р. Л. Адлер утверждает, что оно имеет древнееврейское происхождение.

Дальнейшее чтение

• Чеккерини-Зильберштейн, Т.; Коорнарт, М. (2010). Клеточные автоматы и группы Springer Monographs in Mathematics . Springer Verlag. ISBN 978-3-642-14034-1.
• Линд, Дуглас; Маркус, Брайан (1995). Введение в символическую динамику и кодирование . Кембридж, Великобритания: Cambridge University Press. ISBN 0-521-55900-6.
• Лотер, М. (2002). «Конечные и бесконечные слова». Алгебраическая комбинаторика слов . Кембридж, Великобритания: Cambridge University Press. ISBN 0-521-81220-8. Получено 29.01.2008 .
• Морзе, Марстон ; Хедлунд, Густав А. (1938). «Символическая динамика». Американский журнал математики . 60 (4): 815–866. doi :10.2307/2371264. JSTOR  2371264.
• Sobottka, M. (2022). «Некоторые заметки о классификации пространств сдвига: сдвиги конечного типа; софические сдвиги; и конечно определенные сдвиги». Бюллетень Бразильского математического общества . Новая серия. 53 (3): 981–1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. S2CID  254048586.