| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Группы изометрий формальных языков относительно обобщенных метрик Левенштейна В. О. Янковскийab a Московский государственный университет им. М. В. Ломоносова b Московский центр фундаментальной и прикладной математики
Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 2, Pages DOI: https://doi.org/10.1134/S0001434624070307 
Реферативные базы данных:
 1. ВведениеДанная работа представляет собой частичный ответ на вопрос, какие группы могут быть представлены в виде групп изометрий формальных языков. Прежде, чем перейти к описанию результатов, напомним читателю несколько определений: В статье будут рассмотрены как конечные, так и бесконечные формальные языки. Определение 2. Пусть $(M_1, d_1)$ и $(M_2, d_2)$ – метрические пространства. Будем называть биекцию $\phi\colon M_1 \to M_2$ гомотетией, если существует $t \in \mathbb{R}$ такое, что для любых слов $u, v \in M_1$ выполняется $d_2(\phi(u), \phi(v))=t d_1(u, v)$. Будем называть биекцию $\phi\colon M_1 \to M_2$ изометрией, если для любых элементов $u, v \in M_1$ выполняется $d_2(\phi(u), \phi(v))=d_1(u, v)$. Множество $\operatorname{Isom}_d(M)$ всех изометрий метрического пространства $(M, d)$ в себя образует группу относительно композиции. При этом, группа изометрий метрического пространства всегда изоморфна группе изометрий его образа при гомотетии. Определение 3. Пусть $A$ – конечный алфавит, а слова $u, v \in A^*$. Тогда обобщенное расстояние Левенштейна с весом вставки или удаления $\gamma$ и весом замены $\theta$ между словами $v$ и $u$ равно Здесь и далее мы рассматриваем только такие обобщенные расстояния Левенштейна, у которых веса вставки и удаления равны. Очевидно, что при $\gamma, \theta > 0$ $\operatorname{lev}_{\gamma, \theta}$ – метрика на $A^*$. Наиболее известны следующие частные случаи обобщенной метрики Левенштейна:
Также существует альтернативный способ задания обобщенного расстояния Левенштейна рекуррентной формулой. А именно, имеет место следующее Предложение 1 [2]. Для обобщенного расстояния Левенштейна выполнено соотношение В частности, из этой формулы, а также инвариантности расстояния Левенштейна относительно “отражения” слов, получаем, что $\operatorname{lev}_{\gamma, \theta}(uxv, uyv)=\operatorname{lev}_{\gamma, \theta}(x, y)$. Также всегда выполняются следующие неравенства:
Предложение 2. Пусть $d=\operatorname{lev}_{\gamma_0, \theta_0}$ – обобщенная метрика Левенштейна, а $L$ – произвольный язык. Тогда существует $\theta \in (0, 2]$ такое, что тривиальное отображение $(L, d)$ в $(L, \operatorname{lev}_{1, \theta})$ является гомотетией. Будем обозначать метрику $\operatorname{lev}_{1, \theta}$, как $\operatorname{lev}_\theta$, а группу изометрий языка $L$ относительно нее – как $\operatorname{Isom}_{\theta}(L)$. Здесь и далее $S_n$ обозначает симметрическую группу на $n$ элементах, $C_n$ – циклическую группу порядка $n$, $D_\infty$ – бесконечную диэдральную группу, $\Pi$ – декартово произведение групп. Группы изометрий конечных языков изучались и ранее. Так, например, в [3] доказывается, что для произвольного конечного алфавита $A$, группа изометрий $A^n$ относительно метрики Хэмминга изоморфна $S_{|A|}^n \times S_n$. В некотором смысле продолжением работы Маркова является ряд результатов про группы автоморфизмов отдельных (классов) кодов, представленных в [4] и [5]. Еще одной работой на аналогичную тему является [6], где доказывается, что для произвольного конечного алфавита $A$ и $2 \leqslant k_1 < k_2$ группа изометрий языка $\bigcup_{k= k_1}^{k_2} A^k$ относительно “внутренней метрики Левенштейна” (минимального количества операций вставок, удаления и замены символов, переводящих одно слово в другое таким образом, что все “промежуточные слова” лежат в исходном языке) изоморфна $S_{|A|}^{k_2 - k_1} \times C_2$. В данной же статье исследованы группы изометрий языков, в том числе и бесконечных, относительно семейства обобщенных метрик Левенштейна. В статье доказывается следующая теорема. Теорема 1. Пусть $L$ – произвольный формальный язык, $d$ – произвольная метрика из семейства обобщенных метрик Левенштейна, удовлетворяющая условию, что вес операции замены меньше удвоенного веса операции удаления. Тогда существует $m \in \mathbb{N}$ такое, что для всех слов $w \in L$ и всех изометрий $\phi \in \operatorname{Isom}_d(L)$ выполняется $||\phi(w)| - |w|| \leqslant m$. Заметим, что для обобщенных метрик Левенштейна с весом замены большим или равным удвоенному весу вставки, данное утверждение неверно. Из теоремы 1, в частности, следует, что группа изометрий любого формального языка относительно метрики Левенштейна вкладывается в $\Pi_{n=1}^\infty S_{n}$. Также построен ряд примеров, демонстрирующих, что эта оценка в некотором смысле неулучшаема, причем для языков с разным ростом. Определение 4. Рост языка $L$ – это функция $n \mapsto \bigl|\{w \in L \mid |w| \leqslant n\}\bigr|$. Теорема 2. Пусть $G$ – произвольная конечная группа, $d$ – произвольная метрика из семейства обобщенных метрик Левенштейна. Тогда существуют $n \in \mathbb{N}$ и язык $L \subset \{0, 1\}^{24n}$ такой, что $|L|=n$, $\operatorname{Isom}_d(L) \cong G$ и для любых двух различных слов $u, v \in L$ выполняется $d(u, v) \in \{4, 6\}$. Здесь и далее $A^k$ обозначает множество всех слов длины $k$ над алфавитом $A$. Теорема 3. Пусть $G_1, G_2, \dots $ – счетная последовательность произвольных конечных групп, $d$ – произвольная метрика из семейства обобщенных метрик Левенштейна. Тогда существует язык $L \subset \{0, 1\}^*$ с ростом $O(n)$ такой, что $\operatorname{Isom}_d(L) \cong \Pi_{n=1}^\infty G_n$. Теорема 4. Пусть $d$ – произвольная метрика из семейства обобщенных метрик Левенштейна. Тогда для любого целого $k \geqslant 2$, существует язык $L$ над алфавитом из $k$ символов с ростом $\Theta(k^{\sqrt{n}})$ такой, что Последний факт представляет интерес тем, что полученная группа изометрий по теореме 1 является максимальной для всех языков. Также особое внимание уделяется регулярным языкам. Определение 5. Регулярный язык – формальный язык, который может быть получен из конечных языков применением конечного числа операций объединения ($U \cup V$), произведения ($UV=\{uv\mid u \in U,\, v \in V\}$) и звезды Клини ($L^*=\bigcup_{n=0}^\infty L^n$). В статье доказывается, что их группы изометрий также достаточно разнообразны и данная оценка для них неулучшаема. Теорема 5. Пусть $G$ и $H$ – произвольные конечные группы, $d$ – произвольная метрика из семейства обобщенных метрик Левенштейна. Тогда существует регулярный язык $L \subset \{0, 1\}^*$ такой, что $\operatorname{Isom}_d(L) \cong G \times H^\mathbb{N}$. Теорема 6. Пусть $d$ – произвольная метрика из семейства обобщенных метрик Левенштейна. Тогда существует регулярный язык $L$ такой, что $\operatorname{Isom}_d(L) \cong \Pi_{n=1}^\infty S_{2n}$. Последний факт представляет интерес тем, что полученная группа изометрий по теореме 1 является максимальной для всех языков, не обязательно регулярных. Работа состоит из девяти пунктов (включая введение):
2. Группы изометрий языков над одноэлементным алфавитомПредложение 3. Пусть $L \subset \{a\}^*$, $\theta \in (0, 2]$. Тогда $\operatorname{Isom}_\theta(L)$ либо тривиальна, либо изоморфна циклической группе порядка 2, причем последняя реализуется только как группа изометрий конечных языков. Доказательство. Отображение $l\colon a^n \mapsto n$ является изометрией $(\{a\}^*, \operatorname{lev}_{\theta})$ на метрическое пространство $(\mathbb{N},\, d(m, n)=|n-m|)$. Из этого можно сделать вывод, что $\operatorname{Isom}(L) \cong \operatorname{Isom}(l(L))$.
Обозначим $l(L)$ через $N$; таким образом, $N \subset \mathbb{N}$. Предположим, что $N \subset \mathbb{N}$, $|N| \geqslant 2$ (для $|N|=1$ все очевидно). Пусть $n_0, n_1, \dots $ – элементы $N$, отсортированные по возрастанию, $\phi$ – изометрия из $N$. Покажем, что $\phi(n_0) \in \{n_0, n_{|N|}\}$, где второй вариант реализуется только для конечных языков. В противном случае, если $\phi(n_0)=n_i$, где $i \not\in \{0, |N|\}$, то
$$
\begin{equation*}
\begin{aligned} \, |n_{i+1} - n_{i-1}| &=|\phi^{-1}(n_{i+1}) - \phi^{-1}(n_{i-1})| < |\phi^{-1}(n_{i+1}) - n_0| + |n_0 - \phi^{-1}(n_{i-1})| \\ &=|n_{i+1} - n_i| + |n_{i} - n_{i-1}|=|n_{i+1} - n_{i-1}|. \end{aligned}
\end{equation*}
\notag
$$
Это невозможно.
Пусть $\phi(n_0)=n_0$. Докажем по индукции, что $\phi$ тривиальна. База: $\phi(n_0)=n_0$. Шаг: предположим, что $\phi(n_i)=n_i$ для всех $i < k$. Тогда $n_k$ – единственный ближайший элемент к $n_{k-1}$, не содержащийся в $\{n_0, \dots, n_{k-1}\}$. Следовательно, $\phi(n_k)$ – единственный ближайший элемент к $\phi(n_{k-1})=n_{k-1}$, не содержащийся в $\phi(\{n_0, \dots, n_{k-1}\})=\{n_0, \dots, n_{k-1}\}$, т.е. $\phi(n_k)=n_k$. Пусть $\phi(n_0)=n_{|N|}$. Докажем по индукции, что $\phi\colon n_k \mapsto n_{|N|-k}$. База: $\phi(n_0)=n_{|N|}$. Шаг: предположим, что $\phi(n_i)=n_{|N|-i}$ для всех $i < k$. Тогда $n_k$ – единственный ближайший элемент к $n_{k-1}$, не содержащийся в $\{n_0, \dots, n_{k-1}\}$. Следовательно, $\phi(n_k)$ – единственный ближайший элемент к $\phi(n_{k-1})=n_{|N|-k+1}$, не содержащийся в $\phi(\{n_0, \dots, n_{k-1}\})=\{n_{|N|}, \dots, n_{|N|-k+1}\}$, т.е. $\phi(n_k)=n_{|N|-k}$. Таким образом, никаких других изометрий, кроме этих двух, быть не может (да и вторая реализуется только для конечных языков). Следовательно, $\operatorname{Isom}(L)$ либо тривиальна, либо изоморфна циклической группе порядка 2. Однако уже для двухэлементного алфавита группы изометрий устроены сложнее, что будет продемонстрировано в следующих пунктах. 3. Доказательство теоремы 1, ее следствие и существенность условияЛемма 1 [7]. Не существует бесконечного языка над конечным алфавитом, в котором ни одно слово не входит в другое в качестве подпоследовательности. Будем обозначать как $M(L)$ множество всех минимальных слов в языке $L$ относительно порядка включения в качестве подпоследовательности. Лемма 2. Пусть $L$ – формальный язык, $\theta \in (0, 2)$. Тогда если $\operatorname{Isom}_\theta(L)$ действует на $L$ транзитивно, то $L$ конечен. Доказательство. Пусть $L$ – бесконечный язык, $M(L)$ конечно по лемме 1. Поэтому по принципу Дирихле у $L$ есть бесконечный подъязык с единственным минимальным словом. Обозначим его через $L_0$, а единственное минимальное слово в нем – через $w_0$.
Язык $\{w \in L_0\mid |w| > 2/(2 - \theta)|w_0|\}$ тоже бесконечен. Значит, рассуждая аналогично, у него тоже есть бесконечный подъязык с единственным минимальным словом. Обозначим его через $L_1$, а единственное минимальное слово в нем – через $w_1$. Язык $\{w \in L_1\mid |w| > 2|w_1|\}$ тоже бесконечен. Значит, рассуждая аналогично, у него тоже есть бесконечный подъязык с единственным минимальным словом. Обозначим его через $L_2$, а единственное минимальное слово в нем – через $w_2$. Теперь предположим, что $\operatorname{Isom}_\theta(L)$ действует на $L$ транзитивно. Тогда существует $\phi \in \operatorname{Isom}_\theta(L)$ такая, что $\phi(w_1)=w_0$. Тогда выполняется следующая цепочка неравенств:
$$
\begin{equation*}
\begin{aligned} \, &\operatorname{lev}_\theta(w_0, w_1) + \operatorname{lev}_\theta(w_1, w_2)=\operatorname{lev}_\theta(w_0, w_2)=\operatorname{lev}_\theta(\phi(w_0), \phi(w_2)) \\ &\qquad \leqslant \max\bigl(|\phi(w_0)|, |\phi(w_2)|\bigr) + (\theta - 1) \min\bigl(|\phi(w_0)|, |\phi(w_2)|\bigr) \\ &\qquad \leqslant \theta |w_0| + \max\bigl(\operatorname{lev}_\theta(w_0, \phi(w_0)), \operatorname{lev}_\theta(w_0, \phi(w_2))\bigr) \\ &\qquad\qquad + (\theta - 1)\min\bigl(\operatorname{lev}_\theta(w_0, \phi(w_0)), \operatorname{lev}_\theta(w_0, \phi(w_2))\bigr) \\ &\qquad = \theta |w_0| + \max\bigl(\operatorname{lev}_\theta(w_1, w_0), \operatorname{lev}_\theta(w_1, w_2)\bigr) + (\theta\,{-}\, 1)\min\bigl(\operatorname{lev}_\theta(w_1, w_0), \operatorname{lev}_\theta(w_1, w_2)\bigr) \\ &\qquad =\theta |w_0| + |w_2| - |w_1| + (\theta - 1)(|w_1| - |w_0|) < \operatorname{lev}_\theta(w_0, w_1) + \operatorname{lev}_\theta(w_1, w_2). \end{aligned}
\end{equation*}
\notag
$$
Противоречие. Доказательство теоремы 1. Пусть теперь
$$
\begin{equation*}
m=\max\bigl\{|\phi(v)| - |v|\mid v \in M(L),\, \phi \in \operatorname{Isom}_\theta(L)\bigr\}
\end{equation*}
\notag
$$
(это множество конечно по леммам 1 и 2). Докажем от противного, что для всех слов $w \in L$ и изометрий $\phi \in \operatorname{Isom}_\theta(L)$ выполнено $||w| - |\phi(w)|| \leqslant m$.
Пусть $||w| - |\phi(w)|| > m$. Без ограничения общности будем считать, что $|w| < |\phi(w)|$. Пусть теперь $u \in M(L)$ содержится в $w$ в качестве подпоследовательности. Тогда
$$
\begin{equation*}
\begin{aligned} \, & \operatorname{lev}_\theta(w, u)=\operatorname{lev}_\theta(\phi(w), \phi(u)) \geqslant |\phi(w)| - |\phi(u)| > |w| + m - |\phi(u)| \\ &\qquad\geqslant |w| + |\phi(u)| - |u| - |\phi(u)|=|w| - |u|=\operatorname{lev}_\theta(w, u). \end{aligned}
\end{equation*}
\notag
$$
Противоречие. Доказательство. Пусть $n_1, n_2, \dots $ – порядки орбит естественного действия $\operatorname{Isom}(L)$ на $L$ (орбиты конечны по лемме 2). Поскольку $\operatorname{Isom}(L)$ действует на $L$ эффективно, то она вкладывается в $\Pi_{i=1}^\infty S_{n_i} \leqslant \Pi_{n=1}^\infty S_{n}$. Предложение 4. Существует регулярный язык $L \subset \{0, 1\}^*$ такой, что группа изометрий $\operatorname{Isom}_2(L) \cong D_\infty$, причем она действует на $L$ транзитивно. Доказательство. Рассмотрим регулярный язык $L=1^* \cup 0^*$ и биекцию $\phi\colon L \to \mathbb{Z}$ заданную формулами для всех $n \in \mathbb{N}_0$.
Покажем, что $\phi$ – это изометрия пространств $(L, \operatorname{lev}_2)$ и $(\mathbb{Z},\, d(x, y)=|x - y|)$. Действительно,
$$
\begin{equation*}
\operatorname{lev}_2(0^n, 0^m)=|m - n|, \qquad \operatorname{lev}_2(1^n, 1^m)=|m - n|, \qquad \operatorname{lev}_2(0^n, 1^m)=m + n
\end{equation*}
\notag
$$
для всех $n, m \in \mathbb{N}_0$.
При этом группа изометрий метрического пространства $(\mathbb{Z},\, d(x, y)=|x - y|)$ действует на нем транзитивно и изоморфна $D_\infty$. 4. Растяжение словБудем обозначать расстояние Хэмминга как $h$. Определение 6. Операция растяжения слов – операция $\operatorname{st}\colon A^* \times A^* \to A^*$, заданная рекурсивно: для всех $w_1, w_2 \in A^*, a \in A$. Лемма 3. Пусть слова $w_1, w_2 \in A^*$, причем $|w_1|=|w_2|$. Пусть $k \in \mathbb{N}$, причем $k > h(w_1, w_2)$. Пусть символы $a, b \in A$, причем $a \neq b$. Пусть $\theta \in (0, 2]$. Тогда выполняется равенство Доказательство. Покажем, что найдется минимальный “путь” из $\operatorname{st}(w_1, a^k b a^k)$ в $\operatorname{st}(w_2,$ $ a^k b a^k)$, который не содержит вставок и удалений.
Действительно, допустим, что кратчайший “путь” содержит удаление. Этот “путь” $k$ удалений содержать не может (в противном случае он не будет кратчайшим). Значит, “отрезок” слова между этим удалением и одной из ближайших к нему вставок (с той или с другой стороны) сдвинут на расстояние меньшее $k$. При этом на позициях, не кратных $k + 1$ (нумерация начинается с 1), нет отличных от $a$ символов, а на позициях, сравнимых с $k + 1$ по модулю $2k + 2$, нет отличных от $b$ символов. Значит, если на этом “отрезке” $t$ значимых символов, то на нем также $t-1$ “центральных” символов $b$, которые оказались сдвинуты. Чтобы привести их в порядок, потребуется $2(t - 1)$ операций замены. Значит, суммарная стоимость операций на отрезке (включая исходные удаление и вставку) будет не менее $2(t - 1)\theta + 2$. При этом поэлементная замена всех значимых символов на отрезке без каких-либо вставок и удалений будет стоить $t\theta \leqslant 2(t - 1)\theta + 2$. Так, постепенно меняя пары “вставка / удаление” на замены значимых символов, получим искомый “путь”. 5. Доказательство теоремы 2Лемма 4. Пусть $\Gamma(V, E)$ – конечный простой кубический граф. Тогда существует язык $\{w_v\}_{v \in V} \subset \{0, 1\}^{|E|}$ такой, что Доказательство. Пусть $E=\{e_0, \dots, e_m\}$. Определим $i\colon V\times E \to \{0, 1\}^*$ следующим образом: Определим слово $w_v=i(v, e_0)i(v, e_1)\dots i(v, e_{|E|})$.
Несложно увидеть, что расстояния Хэмминга между словами оказались такими, какими требуется. Теорема 7 [8]. Группа конечна тогда и только тогда, когда она изоморфна группе автоморфизмов некоторого кубического графа. Доказательство теоремы 2. Пусть $G$ – конечная группа, $\Gamma(E, V)$ – кубический граф, соответствующий ей по теореме 7, $L_0$ – язык, построенный для $\Gamma$ по лемме 4, $L_1=\operatorname{st}(L_0, 1^7 0 1^7)$.
Поскольку $\operatorname{diam}(L_1)=6$, то $\operatorname{Isom}_\theta(L_1) \cong G$. При этом длина слов в $L_1$ равна $16|E|=24|V|=24|L_1|$. 6. Доказательство теоремы 3 Доказательство теоремы 3. Пусть $G_1, G_2, \dots $ – счетная последовательность конечных групп. $L_1, L_2, \dots $ – соответствующие языки, построенные по следствию 1. Построим языки $L_1', L_2', \dots $ с помощью рекурсии: где $l_n$ – длина слов в $L_{n}'$.
Несложно увидеть, что группа изометрий $L_n'$ совпадает с группой изометрий $L_n$. Более того, для любых слов $w_n \in L_n'$ и $w_m \in L_m'$, $m > n$, выполняется $\operatorname{lev}_\theta(w_n, w_m)=l(L_m') - l(L_n')$. Это равенство верно, так как для получения более короткого слова из более длинного, достаточно удалить все, кроме префикса $(01)^{l(L_n)}$, а затем из каждого блока $01$ выбрать правильный символ. Из этого следует, что для любой последовательности $\phi_1, \phi_2, \dots $ изометрий языков $L_1', L_2', \dots $ верно, что $\phi\colon w_n \mapsto \phi_n(w_n)$ для всех $n \in \mathbb{N}$, $w_n \in L_n'$ – изометрия $\bigcup_{n=1}^\infty L_n'$. При этом других изометрий у $\bigcup_{n=1}^\infty L_n'$ нет. Действительно, $\Lambda$ переходит в себя как единственное слово без соседей на расстоянии $4$ или $6$. Значит, длина слов в этом языке (т.е. расстояние до $\Lambda$) – инвариант. Иными словами, $\bigcup_{n=1}^\infty L_n'$ имеет рост $O(n)$, так как для любых $n \in \mathbb{N}$ длина всех слов в $L_n'$ больше $24|L_n|$, а значит, $|\{w \in L\mid |w| \leqslant k\}| \leqslant 1 + {k}/{24}$.7. Доказательство теоремы 4 Доказательство теоремы 4. Пусть $A=\{a_1, \dots, a_k\}$ – произвольный алфавит. Построим языки $L_1, L_2, \dots $ рекурсивно: где $l(k, n)$ – длина $L_{n}$.
Заметим, что $l(k, n)=l(k, n - 1) + 2k^{n}(k^{n + 1} + 2)=O(k^{2n})$. При этом $|L_n|= k^{k^n}$. Значит, язык $\bigcup_{n=1}^\infty L_n$ имеет рост $\sum_{l(k, t) \leqslant n} k^{k^t}= \Theta(k^{\sqrt{n}})$. Несложно увидеть, что группа изометрий $L_n$ изоморфна $S_k^{k^n} \times S_{2^n}$. Более того, расстояние между любыми словами $w_n \in L_n'$, $w_m \in L_m$, где $m > n$, равно $l(L_m) - l(L_n)$, так как для получения более короткого слова из более длинного, достаточно удалить все кроме префикса $(a_1\dots a_k)^{l(L_n)}$, а затем из каждого $a_1\dots a_k$ выбрать правильный символ. Из этого следует, что для любой последовательности $\phi_1, \phi_2, \dots $ изометрий языков $L_1, L_2, \dots $ верно, что $\phi\colon w_n \mapsto \phi(w_n)$ для всех $n \in \mathbb{N}$, $w_n \in L_n$ – изометрия $\bigcup_{n=1}^\infty L_n$. При этом других изометрий у $\bigcup_{n=1}^\infty L_n$ нет. Действительно, $\Lambda$ переходит в себя как единственное слово без соседей на расстоянии $1$. Значит, длина слов в этом языке (т.е. расстояние до $\Lambda$) – инвариант. Иными словами, 8. Доказательство теоремы 5 Доказательство. Пусть $u, v \in L$, а $p, q \in \mathbb{N}$. Покажем, что
Действительно, в первом случае более длинное слово получается из более короткого удалением всего лишнего. Во втором случае преобразования достаточно выполнить только над различающимися префиксами. Из этого, в частности, следует, что всякое преобразование вида $\phi\colon u(01)^{kn} \mapsto \psi(k)(u)(01)^{kn} $, где $\psi$ – произвольная функция $\mathbb{N} \to \operatorname{Isom}_\theta(L)$, является изометрией $(L((01)^{n})^*, \operatorname{lev}_\theta)$. Для того, чтобы убедиться в отсутствии других изометрий, заметим, что у $u(01)^{kn}$ имеется ровно $2|L|$ “соседей” на расстоянии $2tn$, при $t \leqslant k$ и ровно $|L|$ при $t > k$. Доказательство теоремы 5. С помощью теоремы 2 мы можем построить равномерные языки $L_1 \subset \{0, 1\}^n$ и $L_2 \subset \{0, 1\}^m$ такие, что
По лемме 3 $\operatorname{Isom}_\theta(L_2((01)^m)^*) \cong H^\mathbb{N}$. Теперь рассмотрим язык $L_1 \cup (01)^{n + m}L_2((01)^m)^*$. Несложно увидеть, что для всех $u \in L_1$, $v \in L_2$, $k \in \mathbb{N}$ имеет место равенство
$$
\begin{equation*}
\operatorname{lev}_\theta\bigl(u, (01)^{n+m}v(01)^{mk}\bigr)=2(n + (k+2)m).
\end{equation*}
\notag
$$
Значит, для всякого $\phi \in \operatorname{Isom}_\theta(L_1)$ и $\psi \in \operatorname{Isom}_\theta(L_2((01)^{mk})^*)$ отображение $\chi$, переводящее все $u \in L_1$ в $\phi(u)$, а все $(01)^{n+m}v$, где $v \in L_2((01)^{mk})^*$, – в $(01)^{n+m}\psi(v)$, является изометрией $L_1 \cup (01)^{n+m}L_2((01)^{mk})^*$. При этом других изометрий быть не может, поскольку слово $v$ из нового языка принадлежит $L_1$ тогда и только тогда, когда у него нет “соседей” на расстоянии превышающем $n$, но меньшем $n + 2m$.
Значит, При этом $L_1 \cup (01)^{n+1}L_2((01)^{mk})^*$ регулярен по построению.9. Доказательство теоремы 6 Доказательство теоремы 6. Рассмотрим язык Покажем, что для произвольных двух слов $u, v \in L$ таких, что $|u| - |v|=6$, $v$ можно получить из $u$ с помощью ровно $6$ удалений. Заметим, что на позициях, номера которых делятся на $3$ (считаем, что нумерация позиций начинается с $0$), в каждом слове может присутствовать только одна единица. Пусть эти особенные единицы в словах $u$ и $v$ будут находиться на позициях $3i$ и $3j$ соответственно. Тогда если $i= j$, достаточно убрать из $u$ суффикс длины $6$ (имеющий вид $010010$). В противном случае из $u$ необходимо сначала убрать подслово $u_{3i}u_{3i+1}u_{3i + 2}=110$, а затем из подслова $u_{3j}u_{3j+1}u_{3j+2}u_{3j+3}=0100$ (нумерация по новому порядку после удаления) убрать $u_{3j}$ и $u_{3j+2}u_{3j+3}$. Таким образом получим $v$.
Из вышедоказанного следует по индукции, что для $u, v \in L$ Таким образом мы видим, что расстояние между словами не зависит ни от чего, кроме их длины. Значит, что для всякой последовательности перестановок $\sigma_i$ элементов $L \cap A^{6i}$ отображение $\phi\colon u \mapsto \sigma_{{|u|}/{6}}(u)$ будет изометрией.В то же время, отсутствие других изометрий следует из того, что каждое слово $u \in L$ имеет ровно ${2|u|}/{3}$ соседей на расстоянии $6$. То есть, поскольку $|L \cap A^{6i}|=2i$, $\operatorname{Isom}_\theta(L) \cong \Pi_{n=1}^\infty S_{2n}$. Автор выражает благодарность Антону Александровичу Клячко и Александру Юрьевичу Ольшанскому за ценные комментарии по работе, а также Алексею Леонидовичу Таламбуце за информацию о статье Хигмана [7], в которой содержится лемма, используемая при доказательстве теоремы 1.
Цитирование в формате AMSBIB
\RBibitem{Yan24} |
|
|||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|