| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Синхронизация конечных автоматов М. В. Волков Уральский федеральный университет
Англоязычная версия:
Russian Mathematical Surveys, 2022, Volume 77, Issue 5, Pages DOI: https://doi.org/10.4213/rm10005e 
Реферативные базы данных:
    ВведениеСинхронизация конечных автоматов – направление дискретной математики, первоначальные понятия которого очень прозрачны, поскольку непосредственно апеллируют к повседневной интуиции. В то же время это направление имеет разнообразные и зачастую неожиданные связи со многими разделами чистой математики и компьютерных наук, а также вполне практические приложения. Его особенная привлекательность состоит в том, что оно быстро приводит к интересным и трудным задачам, среди которых имеется целая россыпь замечательных по простоте формулировки открытых проблем. Идеальным примером здесь может служить гипотеза Черни, обсуждаемая в п. 3.1 ниже: понятия, участвующие в её формулировке, предельно элементарны, но тем не менее уже более полувека ни подтвердить, ни опровергнуть гипотезу не удаётся. В ходе изучения синхронизируемых автоматов наработан обширный материал, который продолжает прирастать впечатляющими темпами. Вышедшие более 10 лет назад обзоры по синхронизируемости [98], [166], [187] заметно устарели. Поэтому естественно попытаться собрать и систематизировать новейшие достижения теории, чтобы вычленить точки её дальнейшего роста. Наряду с этим, уже упомянутая простота исходных понятий делает заманчивой и другую цель – дать доступное неспециалисту изложение начал теории на русском языке. Эта двойственность целей привела к двухслойной структуре текста: в нём развёрнутое представление базовых концепций и основополагающих фактов перемежается более компактно написанными дополнениями, включающими сводки свежих результатов и постановки новых исследовательских задач. Предполагается, что начинающий читатель может пропускать такие дополнения, в то время как эксперт может читать только их, выискивая интересные для себя сведения и вопросы. В процессе работы объём текста быстро рос, и в конечном счёте пришлось поделить его на две статьи. Данная статья ограничивается классическим случаем полных детерминированных автоматов. В разделе 1 вводится понятие синхронизируемости и рассказывается, где и когда оно возникало, – синхронизируемые автоматы часто переоткрывались математиками, информатиками и инженерами. В разделе 2 представлены алгоритмы распознавания синхронизируемости; здесь же обсуждается вычислительная сложность основных проблем, связанных с синхронизацией. В разделе 3 формулируется гипотеза Черни и даётся обзор связанных с ней результатов. В заключительном разделе дан анонс второй статьи цикла, посвящённой другим важным аспектам синхронизируемости. Автор старался излагать ключевые результаты так, чтобы их можно было понять на основе знакомства с началами алгоритмики в духе учебника [55]. Часть обсуждений в разделе 2 использует понятия и результаты теории сложности вычислений в объёме начальных глав учебника [130], но раздел 3 от этих сведений практически не зависит. Список литературы включает только источники, упоминаемые в статье; попытка составить сколько-нибудь полную библиографию по синхронизируемым автоматам противоречила бы аксиоме Козьмы Пруткова “Нельзя объять необъятное”. Заранее приношу извинения тем авторам, чьи публикации не нашли отражения в этом обзоре. Как правило, в список литературы не включались препринты и статьи в трудах конференций, перекрытые последующими журнальными статьями. Статья опирается на конспекты курсов лекций, которые автор читал в разные годы в Уральском федеральном университете и за рубежом. Я признателен слушателям этих лекций за интерес и ценные замечания; особой благодарности заслуживают Грегори Джевенс и Леонид Лагунов. С 2010 г. вместе с Яркко Кари я работал над главой [101] для справочной книги по теории автоматов; я весьма благодарен Яркко как за сотрудничество в работе над этой главой, так и за любезное разрешение включить некоторые материалы из неё в настоящую статью. 1. Синхронизируемые автоматы: что, где, когда?1.1. Конечные автоматы и их графыКонечный автомат – это простое, но чрезвычайно продуктивное понятие, которое отражает очень важную идею взаимодействия объекта с окружающей средой. Есть много разновидностей конечных автоматов; здесь мы имеем дело с самой простой из них: полными детерминированными конечными автоматами. Полный детерминированный конечный автомат (кратко ДКА)– это тройка $\mathscr{A}=\langle Q,\Sigma,\delta \rangle$, где $Q$ – множество состояний, $\Sigma$ – входной алфавит, а $\delta \colon Q \times \Sigma \to Q$ – функция переходов1. Элементы множеств $Q$ и $\Sigma$ называются состояниями и (входными) буквами соответственно. Мы считаем, что ДКА эволюционирует в дискретном времени. В каждый момент времени он находится в определённом состоянии $q\in Q$. В течение следующей единицы времени на вход автомата поступает ровно одна буква $a\in\Sigma$, в результате чего автомат переходит в состояние $\delta(q,a)$. Прокомментируем три прилагательных (полный, детерминированный и конечный) в приведённом выше определении. Атрибут “конечный” относится к тому факту, что как множество состояний, так и входной алфавит всегда предполагаются конечными; мы также по умолчанию предполагаем, что оба эти множества не пусты. Атрибут “детерминированный” означает, что состояние $\delta(q,a)$ однозначно определяется парой $(q,a) \in Q \times \Sigma$, так что правило перехода действительно является функцией. Атрибут “полный” подчёркивает, что функция переходов предполагается полностью определённой: $\delta(q,a)$ должно существовать для каждой пары $(q,a) \in Q \times \Sigma$. Конечные автоматы допускают очень удобное визуальное представление в виде помеченных графов. Мы предполагаем, что читатель знаком с идеей графа; уточним, какие именно графы мы будем использовать. В данной статье граф – это четвёрка множеств и отображений: множество вершин $V$, множество рёбер $E$, отображение $h\colon E \to V$, которое отображает каждое ребро в его начало и отображение $t\colon E \to V $, которое отображает каждое ребро в его конец. Отметим, что в наших графах допускаются рёбра с общим началом и общим концом; такие рёбра называются параллельными. Допускаются и петли (петлёй называют ребро, начало и конец которого совпадают). Таким образом, наши графы на самом деле являются ориентированными мультиграфами, но, поскольку другие виды графов нам не встретятся, мы используем короткий термин. Помеченный граф оснащён дополнительным отображением $E\to \Lambda $, где $\Lambda $ – множество, именуемое алфавитом меток; это отображение ставит в соответствие каждому ребру его метку. Ребро с началом $v$, концом $v'$ и меткой $a$ обозначим знакосочетанием $v\xrightarrow{a}v'$. ДКА $\mathscr{A}=\langle Q,\Sigma,\delta \rangle$ изображается как помеченный граф с множеством вершин $Q$, алфавитом меток $\Sigma$ и множеством рёбер
$$
\begin{equation*}
\{q \xrightarrow{a} q '\mid q,\, q' \in Q, \, a\in \Sigma, \, \delta(q,a)=q'\}.
\end{equation*}
\notag
$$
Таким образом, переход из состояния $q$ в состояние $q'$, вызванный входной буквой $a$, изображается ребром с началом $q$, концом $q'$ и меткой $a$. Например, на рис. 1 изображён ДКА $\mathscr{C}_4$ с четырьмя состояниями 0, 1, 2, 3, двумя входными буквами $a$, $b$ и функцией перехода
$$
\begin{equation*}
\delta(i,a)=\begin{cases} 1, &\text{если}\ i=0, \\ i, &\text{если}\ i=1,2,3; \end{cases}\qquad \delta(i,b)=i+1\!\!\!\!\pmod{4}\text{ для } i=0,1,2,3.
\end{equation*}
\notag
$$
Здесь и далее рёбра с несколькими метками заменяют пучки параллельных рёбер. Так, ребро $0 \xrightarrow{a,b} 1$ на рис. 1 заменяет параллельные рёбра $0 \xrightarrow{a}1$ и $0\xrightarrow{b}1$. Если опустить метки на графе, изображающем некоторый ДКА, получится граф, называемый носителем этого ДКА. Мы свободно применяем понятия и термины теории графов к ДКА, подразумевая, что они применяются к соответствующим носителям. Например, автомат $\mathscr{C}_4$ на рис. 1 сильно связен, поскольку таков его носитель. Словом над алфавитом $\Sigma$ называется конечная (возможно, пустая) последовательность букв из $\Sigma$. За пустым словом закрепим символ $\varepsilon$. Множество всех слов над $\Sigma$, включая $\varepsilon$, обозначается $\Sigma^*$. Оно является моноидом, т. е. полугруппой с единицей относительно операции приписывания слов; единицей этого моноида служит $\varepsilon$. Множество всех непустых слов над $\Sigma$ обозначается $\Sigma^+$. Если $w=a_1 \cdots a_\ell\in\Sigma^+$, то число $\ell$ называется длиной слова $w$ и обозначается через $|w|$. Считаем, что $|\varepsilon|=0$. Функцию переходов $\delta\colon Q\times\Sigma\to Q$ распространяют до функции $Q \times \Sigma^* \to Q$ (по-прежнему обозначаемой $\delta$) следующим образом. Для каждого $q \in Q$ положим $\delta(q,\varepsilon):=q$, и если $w=a_1 \cdots a_\ell$, где $a_1,\dots,a_\ell \in \Sigma$, то
$$
\begin{equation*}
\delta(q,w):=\delta(\ldots\delta(\delta(q,a_1),a_2),\dots,a_\ell).
\end{equation*}
\notag
$$
Когда мы работаем с каким-то фиксированным ДКА, то, как правило, не указываем функцию переходов явно: пишем $\langle Q,\Sigma\rangle$ вместо $\langle Q,\Sigma,\delta\rangle$ и $q \operatorname{.} w$ вместо $\delta(q,w)$. 1.2. Синхронизируемые автоматыОпределение 1.1. Полный детерминированный конечный автомат $\mathscr{A}=\langle Q,\Sigma\rangle$ называется синхронизируемым, если существуют слово $w \in \Sigma^*$ и состояние $s\in Q$ такие, что $q \operatorname{.} w=s$ для всех $q \in Q $. В этом случае слово $w$ называют синхронизирующим и говорят, что оно синхронизирует автомат $\mathscr{A}$ к состоянию $s$. Пример 1.1. Автомат $\mathscr{C}_4$, изображённый на рис. 1, синхронизируем. Утверждение примера 1.1 не совсем тривиально: не так легко угадать синхронизирующее слово для $\mathscr{C}_4$, глядя на рис. 1. Одним из возможных синхронизирующих слов служит $abbbabbba$: оно синхронизирует автомат $\mathscr{C}_4$ к состоянию 1. (Позже мы увидим, что $abbbabbba$ на самом деле является кратчайшим синхронизирующим словом для $\mathscr{C}_4$.) Это следует из непосредственных вычислений, представленных в табл. 1. Таблица 1.Пошаговое применение слова $abbbabbba$ к состояниям автомата $\mathscr{C}_4$
Вычисления, продемонстрированные в табл. 1, поясняют выбор термина “синхронизация”. Представим, что имеются четыре копии автомата $\mathscr{C}_4$, изначально находящиеся в различных состояниях. Если одновременно применить слово $abbbabbba$ к каждой из копий, то они “синхронизируются”, т. е. перейдут в одно и то же состояние (и их дальнейшее поведение при одновременном применении любого другого слова будет оставаться синхронным). Здесь уместен терминологический комментарий. В англоязычной литературе синхронизируемые автоматы обычно называют synchronizing automata или synchronizable automata, а синхронизирующие слова – synchronizing words или reset words. Встречаются и другие термины, например “directable”, “cofinal”, “collapsible”, “resettable”, “recurrent”, “initializable” для синхронизируемых автоматов и “directing”, “recurrent”, “initializing” для синхронизирующих слов. С другой стороны, термин “синхронизация” и его английский аналог часто используются в значениях, отличных от введённого выше. Сразу же зафиксируем очевидное, но полезное свойство синхронизирующих слов. Лемма 1.1. Если слово $w\in\Sigma^*$ синхронизирует ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ к состоянию $s\in Q$, то для любых $u,v\in\Sigma^*$ слово $uwv$ синхронизирует $\mathscr{A}$ к состоянию $s \operatorname{.} v$. На языке алгебры лемма 1.1 означает, что для любого ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ множество $\operatorname{Sync}\mathscr{A}$ всех его синхронизирующих слов образует идеал в моноиде $\Sigma^*$. (Подмножество $I$ моноида $M$ называется идеалом, если $m_1im_2\in I$ для любых $i\in I$ и $m_1,m_2\in M$.) 1.3. Как возникало понятие синхронизируемого автоматаПредставленная выше концепция синхронизируемого автомата оформилась в начале 1960-х гг. В литературе по синхронизируемым автоматам стандартной ссылкой служит статья Яна Черни [44], опубликованная в 1964 г. В действительности по крайней мере два исследователя пришли к тому же понятию несколько раньше. Диссертация Чунг Лаунга Лю [117], выполненная в 1962 г. в Массачусетском технологическом институте, содержит целую главу, посвящённую систематическому изучению синхронизируемых автоматов. Более того, сам термин “синхронизируемый автомат”, по-видимому, происходит именно из этой диссертации: Лю использовал термин “synchronizable”, в то время как Черни пользовался термином “directable”. Лю, с которым (как и с Черни) я консультировался в своих изысканиях по истокам понятия синхронизации, подчеркнул (в электронном письме от 10 марта 2016 г.) роль своего научного руководителя Дина Ардена. Синхронизируемые автоматы появились также в отчётах [112], [113], представленных Артуром Э. Леммелем в Департамент армии США в 1956 и 1963 гг. соответственно; Леммель использовал термин “перезагружаемые машины” (“resettable machines”). Отчёты Леммеля менее проработаны по сравнению с [117] и [44], но второй из них содержит эквивалент ключевого определения 1.1 (правда, только для случая сильно связных автоматов) и некоторые ценные наблюдения. Не исключено, что изучение советских отчётов о НИР, когда таковые будут рассекречены, может добавить к списку первооткрывателей синхронизируемых автоматов и имена отечественных учёных2. В статье Черни [44] понятие синхронизируемого автомата мотивировалось в духе “умозрительных экспериментов” Эдварда Ф. Мура [125]. Мур изучал конечные автоматы с выходом. В автоматах с выходом каждая пара (состояние, входная буква) определяет не только следующее состояние, в которое переходит автомат, но и символ некоторого выходного алфавита, показывающий отклик автомата на действие входной буквы. Автоматы с выходом рассматривались как математические модели устройств, работающих в дискретном режиме (таких как компьютеры, например). Одна из естественных задач, возникающих при таком моделировании, состоит в определении неизвестного внутреннего состояния устройства по откликам этого устройства на различные воздействия. Мур [125] показал, что при определённых условиях состояние автомата однозначно определяется по откликам на подходящую последовательность входных сигналов (называемую экспериментом). Эксперименты Мура были адаптивными, т. е. в них входные сигналы выбирались с учётом откликов на предыдущие сигналы. Сеймур Гинзбург [77] рассмотрел более ограниченные эксперименты, которые он назвал однородными. Однородный эксперимент3 – это просто фиксированная последовательность входных сигналов, т. е. слово над входным алфавитом; таким образом, в экспериментах Гинзбурга отклики использовались только по завершении эксперимента, чтобы установить состояние, в которое перешёл автомат. После этого оставался всего один шаг до постановки той задачи, которой занялся Черни, а именно задачи об определении состояния автомата без какого-либо использования откликов. Отметим, что такая задача отнюдь не является искусственной – имеется много практических ситуаций, когда наблюдать отклики управляемой системы технически сложно или вообще невозможно. В диссертации Лю [117] идея синхронизации мотивировалась тремя задачами. Первая – это задача о приведении автомата, текущее состояние которого неизвестно, к некоторому заданному состоянию, т. е. та же задача, которая мотивировала и Черни. Вторая задача – вариант первой, когда имеется несколько копий данного автомата, первоначально находящихся в разных состояниях, и нужно добиться синхронной работы всех этих копий. Третья задача связана с теорией кодирования – Лю показывает, как синхронизируемые автоматы порождают коды, способные восстановить синхронизацию между отправителем и получателем закодированного сообщения после сбоя в канале передачи информации. Связь синхронизируемых автоматов с кодами действительно имеет первостепенное значение, и мы отдельно обсудим её в следующем разделе. Леммель в [113] использует сходную мотивацию: он, как и Черни, упоминает эксперименты Гинзбурга (со ссылкой на [78]) и, как и Лю, увязывает “перезагружаемые машины” с кодами, в частности с так называемыми эргодическими кодами, рассматривавшимися Марселем-Полем Шютценберже [167]. Кроме того, Леммель проводит аналогию между понятием синхронизируемости и концепцией эргодичности в физике. Неудивительно, что синхронизируемые автоматы были независимо и одновременно (можно сказать, синхронно) придуманы несколькими исследователями: понятие было очень естественно само по себе и хорошо вписывалось в те направления, которое были модны в теории автоматов начала 1960-х гг. В неявной форме феномен синхронизируемости возникал в отдельных исследованиях по автоматам уже с середины 1950-х гг. В качестве примера приведём автомат из классической книги У. Росса Эшби “Введение в кибернетику” [17] (см. с. 60–61 оригинала или с. 92–93 русского перевода). Эшби обсуждает головоломку, в которой нужно утихомирить Певуна и Хохотуна, двух беспокойных духов, обитающих в особняке с привидениями. Каждый из духов может либо шуметь, либо молчать, и их поведение зависит от комбинации двух возможных действий: игры на органе и сжигания ладана. При подходящем выборе обозначений ситуация описывается ДКА с четырьмя состояниями и четырьмя входными буквами, изображённым на рис. 2. Здесь 00 обозначает состояние, когда Певун и Хохотун молчат, 01 обозначает состояние, когда Певун молчит, а Хохотун хохочет, и т. д. Буква $a$ обозначает переход, который происходит, когда на органе не играют и ладан не зажигают, $b$ – переход, вызванный игрой на органе без поджигания ладана, и т,д. Чтобы оба духа умолкли, нужно перевести автомат на рис. 2 в состояние 00. В книге Эшби эта головоломка решена при дополнительном предположении, что оба духа активны, т. е. автомат находится в состоянии 11; предложенное решение описывается словом $acb$. Однако, как читатель может легко убедиться, автомат Эшби синхронизируем4, и слово $acb$ синхронизирует его к состоянию 00. Поэтому дополнительное предположение несущественно, и применение соответствующей последовательности действий заставит Певуна и Хохотуна замолчать при любом их первоначальном поведении! С 1960-х гг. понятие синхронизируемого автомата часто переоткрывалось. Одной из причин этого было то, что работы первопроходцев [44], [112], [113], [117] были труднодоступны. Статья Черни [44] была опубликована на словацком языке в местном журнале. Диссертация Лю [117] целиком не публиковалась; часть её вошла в статью [116], но результаты по синхронизации Лю в эту статью, к сожалению, не включил. Из-за этого его вклад в теорию синхронизируемых автоматов не стал широко известным и в конечном итоге был надолго забыт5. Отчёты Леммеля [112], [113], как и последующий отчет Леммеля и Бьюлы Раднер [114], выполнявшиеся по контракту армейского ведомства США, не были предназначены для широкого распространения (хотя и не были секретными). Более концептуальной причиной переоткрытия синхронизируемых автоматов было то, что время от времени они неожиданно “всплывали” в разнообразных областях математики, информатики и технических наук, весьма далёких от тех задач, которые мотивировали работы [44], [112], [113], [117]. Мы приведём два примера такого рода в п. 1.5 и п. 1.6, после краткого обсуждения роли синхронизируемых автоматов в теории кодирования. В рамках этой теории синхронизация автоматов изучалась уже с середины 1950-х гг. (см., например, уже цитированные работы Шютценберже [167] и Леммеля [112]), т. е. до того, как было дано общепринятое теперь определение синхронизируемого автомата. 1.4. Синхронизируемые автоматы и кодыЗдесь мы обсудим взаимосвязи между синхронизируемыми автоматами и кодами на идейном уровне, не предполагая никаких предварительных знаний из теории кодов6. Говоря о кодировании, мы имеем в виду следующее. Имеются данные, представленные длинным словом над некоторым алфавитом $\Theta$. Хорошим примером может служить какой-нибудь текст на естественном языке, скажем, роман Марселя Пруста “В поисках утраченного времени”, французский оригинал которого содержит примерно 9 609 000 знаков (каждая буква, знак препинания и пробел считаются за один знак). Для хранения или передачи таких данных их кодируют, заменяя каждый знак алфавита $\Theta$ словом над некоторым другим алфавитом $\Sigma$, обычно над двоичным алфавитом $\{0,1\}$. Итак, кодирование – это отображение $\chi\colon\Theta\to\Sigma^+$ такое, что продолжение $\chi$ на $\Theta^+$ инъективно, т. е. каждое слово $w\in\Theta^+$ однозначно определяется тем словом из $\Sigma^+$, которое получится, если последовательно заменять каждую букву $a$ слова $w$ на слово $a\chi$. Множество $\Theta\chi$ называется кодом, а его элементы – кодовыми словами. Кодирование $\chi\colon\Theta\to\{0,1\}^+$ называют двоичным. Любое двоичное кодирование алфавита $\Theta$ с помощью слов постоянной длины (таких как ANSII-коды, например) требует $\lceil\log_2|\Theta|\rceil$ бит для каждой буквы. Следовательно, чтобы закодировать данное слово $w\in\Theta^+$, потребуется $|w|\cdot \lceil\log_2|\Theta|\rceil$ бит. Во многих случаях, однако, буквы неравноправны – одни встречаются чаще, другие реже. (Скажем, в упомянутом романе Пруста “e” встречается примерно вдвое чаще, чем “a”, а частота появления “k” составляет менее 0.9% от частоты появления “l”.) Поэтому можно сэкономить память (в случае хранения данных) и/или время (в случае передачи данных), если отказаться от равенства длин кодовых слов и кодировать буквы из $\Theta$, которые встречаются чаще, более короткими словами над $\Sigma$. Эта простая идея использовалась ещё в XIX в. в телеграфном коде Сэмюэля Морзе: так, “e”, самая распространённая буква английского языка, имеет самый короткий код Морзе (одну точку). С другой стороны, при использовании кодовых слов различной длины может стать нетривиальной задача декодирования, т. е. восстановления слова $w\in\Theta^+$ по последовательности кодов его букв. Приведём простейший пример. Нетрудно проверить, что отображение $\chi\colon\{a,b\}\to\{0,1\}^+$, определённое правилом $a\chi:=0$, $b\chi:=01$, будет кодированием. Допустим, что в декодер поступает последовательность из 0 и 1, начинающаяся с 0. Прочитав первый бит, декодер ещё не сможет определить, является ли данный 0 кодом буквы $a$ или первым битом кода буквы $b$, и будет должен отложить решение до прочтения следующего бита, а прочитанный бит придётся до этого запомнить. При более сложном кодировании такая задержка декодирования может быть значительной и по времени, и по памяти, требуемой для хранения промежуточных данных. Есть, однако, важный класс кодов, допускающих декодирование “на лету”, т. е. с той же скоростью, с которой поступают кодовые слова. Назовём слово $x\in\Sigma^*$ префиксом слова $y\in\Sigma^+$, если $y$ можно представить как $y=xz$ для некоторого $z\in\Sigma^+$. (Заметим, что в соответствии с этим определением $\varepsilon$ будет префиксом слова $y$, а вот само слово не является своим префиксом.) Множество $X\subset\Sigma^+$ называется префиксным кодом, если слова из $X$ не являются префиксами друг друга; кодирование $\chi\colon\Theta\to\Sigma^+$ называют префиксным, если $\Theta\chi$ – префиксный код. При префиксном кодировании процедура декодирования очень проста: декодер читает поступающий поток символов из $\Sigma$ слева направо, пока не прочтёт кодовое слово. Это слово не может быть префиксом никакого другого кодового слова в силу определения префиксного кода, поэтому прочитанное слово сразу заменяется соответствующей буквой из $\Theta$ и удаляется из потока, после чего процесс повторяется. Классический результат теории кодирования (теорема Крафта–Макмиллана, см. [29; теорема 2.4.12]) гарантирует, что для любого кода найдётся префиксный код над тем же алфавитом с тем же набором длин кодовых слов. Отсюда следует, что наилучшее сжатие данных, возможное за счёт использования кодов переменной длины, реализуемо префиксным кодом. Это – наряду с отсутствием задержек декодирования – объясняет, почему в приложениях, как правило, встречаются именно префиксные коды. Описанный выше алгоритм декодирования изящно реализуется конечным автоматом, вообще говоря частичным7. Мы обсудим соответствующее построение во второй статье цикла; сейчас же ограничимся специальным случаем конечных максимальных префиксных кодов. (Префиксный код $X\subset\Sigma^+$ называется максимальным, если $X$ не содержится ни в каком другом префиксном коде над $\Sigma$.) Если $X$ – такой код, то в качестве его декодера используется ДКА $\mathscr{A}_X=\langle Q,\Sigma\rangle$, где $Q$ – множество всех префиксов слов из $X$, а функция перехода определена так:
$$
\begin{equation*}
q \operatorname{.} a:=\begin{cases} qa, & \text{если}\ qa \text{ - префикс слова из}\ X, \\ \varepsilon, & \text{если}\ qa \in X. \end{cases}
\end{equation*}
\notag
$$
Автомат $\mathscr{A}_X$ начинает работу в состоянии $\varepsilon$ и разделяет поступающий поток символов из $\Sigma$ на кодовые слова, соответствующие возвратам в это состояние. На рис. 3 изображён ДКА $\mathscr{A}_C$ для максимального префиксного кода Максимальный префиксный код $X$ над $\Sigma$ называют синхронизированным, если существует такое слово $z\in\Sigma^+$, что для любого $y\in\Sigma^*$ слово $yz$ можно разложить в произведение слов из $X$. Такое $z$ называется синхронизирующим словом для $X$. Преимущество синхронизированных кодов состоит в том, что при сбое синхронизации между декодером и кодером, вызванном ошибками передачи, достаточно передать синхронизирующее слово, и последующие символы будут декодированы верно. Более того, поскольку вероятность того, что слово $x \in\Sigma^*$ содержит фиксированный блок $z$, стремится к 1 с ростом длины $x$, синхронизированные коды восстанавливают синхронизацию сами по себе после передачи достаточного количества символов. (Как показано в [39], последнее свойство фактически характеризует синхронизированные коды.) Проиллюстрируем это понятие на примере кода $C$ из (1). Легко проверить, что каждое из слов 010, 011110, 011111110, … является синхронизирующим для $C$. Предположим, что было отправлено кодовое слово 000, но первый бит исказился при передаче и в результате было получено слово 100. Декодер, который не может знать об ошибке, интерпретирует 10 как кодовое слово и, таким образом, теряет синхронизацию, поскольку станет обрабатывать следующий бит как часть другого кодового слова. Казалось бы, с этого момента всё дальнейшее декодирование будет неверным, однако это не так. С высокой вероятностью потеря синхронизации не распространится слишком далеко: синхронизация восстановится, как только декодер встретит в принимаемом потоке один из блоков 010, 011110, 011111110, … . Несколько примеров указаны в табл. 2. (Вертикальные линии в табл. 2 не являются частью передаваемых данных и приведены только для удобства, чтобы показать разделение каждого потока на кодовые слова.) Кодовые слова, выделенные жирным шрифтом, указывают блоки, начиная с которых синхронизация восстанавливается. Таблица 2.Восстановление синхронизации при использовании кода $C$ из (1)
Сходство терминологии намекает на родство синхронизированных кодов и синхронизируемых автоматов, и действительно, эти два понятия тесно связаны. В том специальном случае, который мы рассматриваем сейчас, их связь носит особенно непосредственный характер, как показывает следующий легко проверяемый результат. Предложение 1.1. Максимальный префиксный код синхронизирован тогда и только тогда, когда синхронизируем его декодер. При этом слова, синхронизирующие код $X$, – это в точности слова, которые синхронизируют ДКА $\mathscr{A}_X$ к состоянию $\varepsilon$. Декодеры синхронизированных кодов образуют важный подкласс класса синхронизируемых автоматов, и изучению этого подкласса до сих пор уделяется значительное внимание (см., например, недавние публикации [28], [30]–[33], [89], [161]). 1.5. Переоткрытие в промышленной механикеЗадачи синхронизации естественным образом возникают в промышленной механике при разработке устройств, осуществляющих различные манипуляции с деталями (подача, сортировка, упаковка и т. п.). В русле этой проблематики понятие синхронизируемого автомата было независимо переоткрыто в середине 1980-х гг. Баласом Натараджаном [126], [127], показавшим, как такие автоматы могут быть использованы для создания чисто механических ориентаторов плоских многоугольных деталей. Мы объясним суть этого подхода с помощью иллюстративного примера, взятого из [10]. Пусть деталь некоторого устройства имеет форму, показанную на рис. 4. На точку сборки такие детали должны поступать в определённой ориентации. Для простоты предположим, что возможны только четыре исходные ориентации деталей, а именно те, которые изображены на рис. 5. Далее, предположим, что к моменту сборки деталь должна быть сориентирована выступом влево (вторая слева ориентация на рис. 5). Ориентатор должен сориентировать деталь нужным образом при любом её первоначальном положении. Есть разные подходы к конструированию ориентаторов, но на практике предпочтительны простые и надёжные механические ориентаторы, которые не требуют сенсорных датчиков, машинного зрения и т. п. В нашем примере цель достигается следующим образом. Поместим детали на ленту транспортёра, которая доставит их к месту сборки, а вдоль ленты разместим ряд пассивных препятствий. Понадобятся препятствия двух типов: длинные и короткие. Длина длинного препятствия выбирается так, чтобы любая деталь на ленте натыкалась на это препятствие своим нижним правым углом (мы предполагаем, что лента движется слева направо). При этом деталь, увлекаемая лентой, поворачивается на $90^\circ$ по часовой стрелке, как показано на рис. 6. Короткое препятствие оказывает тот же эффект, когда деталь ориентирована выступом вниз (первая слева ориентация на рис. 5) и препятствие зацепляет выступ; в противном случае оно не касается детали, и та проходит мимо препятствия, не меняя ориентацию. Схема на рис. 7 показывает, как препятствия влияют на ориентацию детали. Надеемся, что читатель узнал здесь автомат $\mathscr{C}_4$ (ср. с рис. 1). Поскольку слово $abbbabbba$ синхронизирует $\mathscr{C}_4$ к состоянию 1 (см. обсуждение примера 1.1 в п. 1.2), при прохождении последовательности препятствий
$$
\begin{equation*}
\begin{gathered} \, \text{короткое}-\text{ДЛИННОЕ}-\text{ДЛИННОЕ}-\text{ДЛИННОЕ}-\text{короткое}- \\ \text{ДЛИННОЕ}-\text{ДЛИННОЕ}-\text{ДЛИННОЕ}-\text{короткое} \end{gathered}
\end{equation*}
\notag
$$
любая деталь примет нужную ориентацию. С 1990-х гг. разработка устройств подачи и сортировки на основе синхронизируемых автоматов развилась в обширное исследовательское направление, но справедливо сказать, что большинство публикаций в этой области касается технических аспектов. Однако некоторые из этих публикаций содержат и важные для теории результаты – см., например, [46], [64], [79], [143]. 1.6. Переоткрытие в теории подстановочных системВ 1990-х гг. синхронизируемые автоматы были ещё раз переоткрыты в теории подстановок. Подстановка на конечном алфавите $X$ – это отображение $\sigma\colon X \to X^+$. Теория подстановок изучает динамические аспекты итераций подстановок на множествах самой разной природы (см. коллективную монографию [140]). Говорят, что $\sigma\colon X \to X^+$ – подстановка постоянной длины, если длины слов $x\sigma$ одинаковы для всех $x\in X$. Такие подстановки используются, например, для порождения фрактальных объектов; в качестве иллюстрации приведём изящное построение кривой Пеано (непрерывной кривой, заполняющей единичный квадрат), принадлежащее Элиакиму Муру [124]. Идея Мура понятна из рис. 8 [124; рис. 3]. Для удобства обозначения направлений повернём единичный квадрат из левой части рис. 8 на $45^\circ$ по часовой стрелке, как показано на рис. 9. Видно, что ломаная, с которой Мур начинает построение, состоит из 9 звеньев (обозначенных на рис. 9 стрелками). Эти звенья проходятся с левого угла квадрата в последовательности ENESWSENE, где буквы E, N, W и S обозначают стороны света. На каждой последующей итерации каждая стрелка заменяется аналогичной 9-звенной ломаной, т. е. производится подстановка постоянной длины 9 по правилу
$$
\begin{equation*}
\begin{aligned} \, \mathrm{E} &\mapsto \mathrm{ENESWSENE}, \\ \mathrm{N} &\mapsto \mathrm{NWNESENWN}, \\ \mathrm{W} &\mapsto \mathrm{WSWNENWSW}, \\ \mathrm{S} &\mapsto \mathrm{SESWNWSES}. \end{aligned}
\end{equation*}
\notag
$$
Искомая кривая Пеано есть предел построенной так последовательности ломаных. Говорят, что подстановка постоянной длины $\sigma\colon X \to X^+$ удовлетворяет условию совпадения (coincidence condition), если существуют такие натуральные $m$ и $k$, что в $m$-й позиции слов $x\sigma^k$ для всех $x\in X$ стоит одна и та же буква. В качестве примера рассмотрим подстановку $\tau$ на $X:=\{0,1,2\}$, определённую правилом Вычисляя итерации $\tau$ до $\tau^4$ (см. табл. 3), мы видим, что $\tau$ удовлетворяет условию совпадения с $k=4$, $m=7$.Таблица 3.Подстановка, удовлетворяющая условию совпадения
Фредерик Мишель Деккинг [59] показал, что условие совпадения играет ключевую роль для характеризации ряда важных свойств динамических систем, определяемых подстановками постоянной длины (см. обзор в [140; гл. 7]). Для нас же условие совпадения интересно как очередная инкарнация синхронизируемости. Чтобы увидеть это, установим взаимно однозначное соответствие между ДКА и подстановками постоянной длины. ДКА $\mathscr{A}=\langle Q,\Sigma,\delta\rangle$ с алфавитом $\Sigma=\{a_1,\dots,a_\ell\}$ определяет подстановку постоянной длины $\ell$ на множестве $Q$ по следующему правилу: $q\!\in\! Q$ отображается в слово $(q \operatorname{.} a_1)\cdots (q \operatorname{.} a_\ell)\!\in\! Q^+$. Например, автомат $\mathscr{C}_4$ (см. рис. 1) определяет подстановку
$$
\begin{equation*}
0\mapsto 11,\quad 1\mapsto 12,\quad 2\mapsto 23,\quad 3\mapsto 30.
\end{equation*}
\notag
$$
Обратно, каждая подстановка $\sigma\colon X\to X^+$ такая, что $|x\sigma|=\ell$ для всех $x\in X$, определяет ДКА с множеством состояний $X$ и $\ell$ входными буквами $a_1,\dots,a_\ell$, действующими на $X$ по правилу: $x \operatorname{.} a_i$ – это символ в $i$-й позиции слова $x\sigma$. Например, подстановка (2) определяет автомат, изображённый на рис. 10. Несложно видеть, что при указанном взаимно однозначном соответствии подстановки, удовлетворяющие условию совпадения, в точности соответствуют синхронизируемым автоматам. При этом номер итерации, на которой впервые появляется совпадение, равен минимальной длине синхронизирующего слова для соответствующего ДКА. Эти наблюдения были впервые сделаны, по-видимому, Дирком Фретлё и Берндом Сингом в [71]; Фретлё и Синг пользовались отличной от принятой здесь терминологией, поскольку не были знакомы с понятием синхронизируемого автомата (и переоткрыли некоторые результаты Черни [44]). 1.7. Алгебраические аспектыДля ДКА $\mathscr{A}=\langle Q,\Sigma,\delta\rangle$ каждое слово $w\in\Sigma^*$ определяет преобразование $[w]\colon Q\to Q$ по правилу $[w]\colon q\mapsto q \operatorname{.} w$. Обозначим совокупность всех таких преобразований через $M(\mathscr{A})$. Ясно, что множество $M(\mathscr{A})$ всегда содержит тождественное преобразование $[\varepsilon]$ и замкнуто относительно умножения преобразований: для любых слов $u,v\in\Sigma^*$ имеем $[u][v]=[uv]$, где $uv$ – произведение $u$ и $v$ в $\Sigma^*$, т. е. результат приписывания $v$ к $u$. Поэтому $M(\mathscr{A})$ – подмоноид в моноиде $\mathcal{T}(Q)$ всех преобразований множества $Q$; он называется моноидом переходов автомата $\mathscr{A}$. Если трактовать конечный автомат как вычислительное устройство, то моноид переходов можно мыслить себе как библиотеку программ этого устройства, содержащую описания всех доступных ему вычислений. Рангом преобразования конечного множества называют число элементов в образе этого преобразования. Итак, преобразования ранга 1 – это в точности константные преобразования, переводящие все элементы исходного множества в один и тот же элемент. Теперь понятно, как синхронизируемость ДКА выражается в терминах его моноида перехода: ДКА $\mathscr{A}$ синхронизируем тогда и только тогда, когда в моноиде $M(\mathscr{A})$ имеется преобразование ранга 1. Возможность рассматривать феномен синхронизируемости как с комбинаторной, так и с алгебраической точки зрения нередко бывает полезной. В частности, алгебраический подход допускает естественную линеаризацию, что позволяет задействовать арсенал линейной алгебры. А именно, пусть $Q=\{q_1,\dots,q_n\}$. Состоянию $q_i$ поставим в соответствие вектор
$$
\begin{equation*}
[q_i]=(\underbrace{0,\dots,0}_{i-1},1,\underbrace{0\dots,0}_{n-i})
\end{equation*}
\notag
$$
пространства $\mathbb{R}^n$ всех $n$-мерных строк над полем $\mathbb{R}$ действительных чисел. Тогда векторы $[q_1],\dots,[q_n]$ образуют базис в $\mathbb{R}^n$, и для каждого слова $w\in\Sigma^*$ преобразование $[w]\in M(\mathscr{A})$ однозначно продолжается до линейного оператора пространства $\mathbb{R}^n$. Ставя в соответствие преобразованию $[w]$ матрицу этого оператора в указанном базисе, мы превращаем $M(\mathscr{A})$ в моноид $(n\times n)$-матриц. Синхронизируемость автомата $\mathscr{A}$ означает в точности наличие в этом моноиде матрицы, в которой один столбец состоит из единиц, а все остальные столбцы нулевые. Такая линеаризация эффективно использовалась в доказательствах нескольких ключевых результатов, которые обсуждаются в п. 3.4. Описанная линеаризация есть не что иное, как линейное представление моноида $M(\mathscr{A})$ над полем $\mathbb{R}$, которое при необходимости можно считать и представлением над полем комплексных чисел. Изучение синхронизируемых автоматов средствами теории представлений принесло ряд содержательных результатов. Пионером в этом направлении был, по-видимому, И. К. Рысцов [152]; из других публикаций, в которых к синхронизируемым автоматам прилагались методы теории представлений, можно отметить статьи Жоржи Алмейды, Эмануеле Родаро, Бенджамина Стейнберга и их соавторов [3]–[5], [16], [147], [172]. С моноидами преобразований, а точнее, с их группами обратимых элементов связано одно направление теории синхронизируемых автоматов, ставшее в последнее время популярным среди специалистов по группам перестановок. Обозначим через $\mathcal{S}(Q)$ симметрическую группу на множестве $Q$, т. е. группу всех перестановок $Q$. Подгруппу $\mathcal{G}$ группы $\mathcal{S}(Q)$ называют синхронизирующей, если для любого преобразования $\theta\in\mathcal{T}(Q)\setminus\mathcal{S}(Q)$ подмоноид, порождённый $\mathcal{G}$ и $\theta$, содержит преобразование ранга 1. На языке автоматов это означает, что наличие $\mathcal{G}$ в качестве подгруппы в группе обратимых элементов моноида $M(\mathscr{A})$ гарантирует синхронизируемость ДКА $\mathscr{A}$ при условии, что среди входных букв этого автомата хотя бы одна не действует как перестановка множества состояний. Примерами синхронизирующих групп являются сама симметрическая группа, знакопеременная группа и, вообще, любая дважды транзитивная8 группа перестановок. Это легко следует из критерия синхронизируемости (см. предложение 2.1 ниже). С другой стороны, нетрудно видеть, что синхронизирующая подгруппа в $\mathcal{S}(Q)$ должна быть примитивной, т. е. не может сохранять никакое разбиение множества $Q$ на несколько неодноэлементных блоков. Итак, понятие синхронизирующей группы выделяет подкласс класса примитивных групп, содержащий все дважды транзитивные группы. Задача о точной характеризации этого подкласса оказалась весьма содержательной, обнаружила ряд глубоких связей с теорий классических комбинаторных конфигураций (таких как латинские квадраты, системы Штейнера, матрицы Адамара и т. п.) и породила большое число публикаций. Обзор работ, связанных со (всё ещё не завершённой) классификацией синхронизирующих групп, не включён в настоящую статью, поскольку этот материал обстоятельно представлен в недавнем мемуаре Жоау Араужу, Питера Камерона и Бенджамина Стейнберга [15]. Завершая этот короткий экскурс в алгебру, заметим ещё, что и сами автоматы можно естественным образом интерпретировать как алгебраические структуры. Напомним, что алгеброй типа $(n_1,n_2,\dots)$ с носителем $Q$ называется непустое множество $Q$, оснащённое операциями
$$
\begin{equation*}
f_1 \colon \underbrace{Q \times Q \times\dots\times Q}_{n_1} \to Q,\quad f_2 \colon \underbrace {Q \times Q \times\dots\times Q}_{n_2} \to Q, \quad\dots\,.
\end{equation*}
\notag
$$
Алгебра $(Q;f_1,f_2,\dots)$ типа $(1,1,\dots)$ называется унаром. Понятно, что ДКА $\mathscr {A}=\langle Q,\Sigma\rangle $ – не что иное, как унар с носителем $Q$, на котором для каждой буквы $a \in \Sigma$ определена унарная операция по правилу $[a] \colon q \mapsto q \operatorname{.} a$. Такая точка зрения позволяет применять к автоматам стандартные алгебраические понятия подалгебры (подавтомата), конгруэнции, факторавтомата и т. п.; мы пользуемся ими ниже. Отметим, что класс синхронизируемых ДКА замкнут относительно взятия подавтоматов и факторавтоматов; при этом каждое слово, синхронизирующее данный ДКА, будет синхронизировать все его подавтоматы и факторавтоматы. При интерпретации автоматов как унаров понятие синхронизируемого автомата достаточно естественно переводится на язык алгебры. Напомним, что унарный терм – это выражение $\tau$ вида $x \operatorname{.} w$, где $x$ – переменная, а $w$ – слово над алфавитом $\Sigma$. Тождество унаров – это формальное равенство двух унарных термов. ДКА $\mathscr {A}=\langle Q,\Sigma\rangle$, рассматриваемый как унар, удовлетворяет тождеству $\tau_1=\tau_2$, если термы $\tau_1$ и $\tau_2$ принимают одно и то же значение при каждой интерпретации их переменных в множестве $Q$. Тождества унаров могут иметь вид $x \operatorname{.} u=x \operatorname{.} v$ (однородные тождества) или $x \operatorname{.} u=y \operatorname{.} v$, где $x \ne y$ (неоднородные тождества). Легко понять, что ДКА синхронизируем тогда и только тогда, когда он удовлетворяет неоднородному тождеству. Действительно, если слово $w$ синхронизирует ДКА $\mathscr {A}$, то $\mathscr {A}$ удовлетворяет неоднородному тождеству $x \operatorname{.} w=y \operatorname{.} w$. Обратно, пусть $\mathscr {A}$ удовлетворяет какому-то неоднородному тождеству $x \operatorname{.} u=y \operatorname{.} v$. Заменив в нём $x$ на $y$, получим тождество $y \operatorname{.} u=y \operatorname{.} v$, и по транзитивности в $\mathscr {A}$ выполняется и тождество $x \operatorname{.} u=y \operatorname{.} u$. Последнее тождество означает, что слово $u$ синхронизирует $\mathscr {A}$. Итак, синхронизируемые автоматы при желании можно изучать в рамках эквациональной логики унаров. Пока нельзя сказать, чтобы такой подход принёс сколько-нибудь заметную пользу для понимания комбинаторной сути синхронизируемости; тем не менее в его рамках выполнено немало публикаций (см. обзор Стояна Богдановича, Балажа Имре, Мирослава Чирича и Татьяны Петкович [34]). 1.8. Другие приложения и связиЕсли читатель добрался до этого пункта, можно надеяться, что он уже убедился в том, что понятие синхронизируемого автомата хорошо мотивировано, а области, в которых возникают синхронизируемые автоматы, весьма разнообразны. Здесь перечислены ещё несколько примеров задач, так или иначе связанных с синхронизацией ДКА. То, что эти задачи лишь перечисляются, а не обсуждаются в деталях в стиле предыдущих пунктов, совсем не означает, что они менее важны или менее увлекательны! Синхронизирующие слова давно применяются при тестировании схем и протоколов (см. статьи [36], [53], [54], [136], [145] в качестве типовых примеров исследований в этой области, а также обзор [166]). Когда испытуемая система подверглась очередному тесту, то перед следующим испытанием её нужно вернуть к первоначальному состоянию – в этом и состоит роль синхронизирующих слов. В аналогичной роли синхронизирующие слова используются в задачах планирования движения в роботике, когда “заблудившийся” робот должен вернуться в известную позицию (см., например, [175]). На противоположном, теоретическом конце спектра находятся связи синхронизируемых автоматов с алгеброй и логикой. Соотношения между синхронизируемыми автоматами и функциями многозначной логики активно изучались в школе Арто Саломаа (см. его собственные статьи [162]–[165] и обзор [122]). Некоторые задачи теории конечных полугрупп [6], [137] мотивировали интерес к универсальным синхронизирующим словам, т. е. словам, синхронизирующим все синхронизируемые автоматы с данным числом состояний над фиксированным алфавитом. Обзор результатов по универсальной синхронизации на середину 2000-х гг. см. в [9], [47]; среди более поздних публикаций в этом направлении см. [48]–[51]. В заключение раздела проясним одно недоразумение. В литературе нередко можно встретить заявления о применениях синхронизируемых автоматов в биоинформатике, подкрепляемые ссылками на статьи [20], [21]. В этих, без сомнения очень интересных и важных, работах сообщаются результаты успешных экспериментов по созданию автоматов молекулярного размера, в которых и состояния, и входные буквы представляют собой короткие цепочки ДНК. Так, в [20] описан “автоматный бульон” – раствор, каждый миллилитр которого содержит $3\cdot 10^{12}$ идентичных микроавтоматов. Идея о том, что в перспективе такого рода системами молекулярных автоматов можно будет управлять, “приправляя” соответствующий бульон цепочками ДНК, кодирующими синхронизирующие слова, была высказана как гипотеза в обзоре [187]. Однако в [187] никоим образом не утверждалось, что эта высказанная с эпитетом “yet imaginary” идея уже реализована в [20], [21] или в каких-либо других реальных экспериментах. (На самом деле молекулярные автоматы, построенные в [20], [21], не являются синхронизируемыми!) Отметим, что содержательные связи между синхронизируемыми автоматами и биоинформатикой существуют (см., например, [35]); они обсуждаются в разделе второй статьи цикла, посвящённом синхронизации частичных детерминированных автоматов. 2. Алгоритмические и сложностные аспекты2.1. Проверка автомата на синхронизируемостьПонятно, что не все ДКА синхронизируемы, и потому возникает вопрос, как узнать, синхронизируем ли данный автомат. Ответ может быть получен с помощью конструкции автомата подмножеств из классической статьи Майкла О. Рабина и Даны Скотта [141]. В учебниках по теории автоматов эта конструкция обычно используется для детерминизации недетерминированных автоматов (она даёт ДКА, распознающий тот же язык, что и данный недетерминированный автомат), но здесь мы применим её к детерминированным автоматам. Обозначим через $\mathcal{P}(Q)$ множество всех непустых подмножеств множества $Q$. Функция переходов автомата $\mathscr{A}=\langle Q,\Sigma,\delta\rangle$ распространяется до функции $\mathcal{P}(Q)\times\Sigma\to\mathcal{P}(Q)$, за которой мы сохраним обозначение $\delta$, по правилу $\delta(P,a):=\{\delta(p,a)\mid p\in P\}$ для всех множеств $P\in\mathcal{P}(Q)$ и всех букв $a\in\Sigma$. Возникает ДКА $\mathcal{P}(\mathscr{A})=\langle\mathcal{P}(Q),\Sigma,\delta\rangle$, который называется автоматом подмножеств автомата $\mathscr{A}$. На рис. 11 изображён автомат подмножеств автомата $\mathscr{C}_4$ (см. рис. 1). Применяя к автомату подмножеств $\mathcal{P}(\mathscr {A})=\langle \mathcal{P}(Q),\Sigma,\delta\rangle$ соглашение, введённое в п. 1.1, будем писать $P \operatorname{.} v$ вместо $\delta(P,v)$ (здесь $P$ – непустое подмножество в $Q$, а $v$ – слово над $\Sigma$). Тогда ясно, что слово $w\in\Sigma^*$ синхронизирует ДКА $\mathscr{A}$ в том и только том случае, если множество $Q \operatorname{.} w$ одноэлементно. Чтобы выразить последнее свойство в терминах носителя автомата $\mathcal{P}(\mathscr {A})$, напомним некоторые понятия из теории графов. В соответствии с определением из п. 1.1, граф – это четвёрка множеств и отображений $ \langle V,E,h,t \rangle$, где $V$ и $E$ – это соответственно множества вершин и рёбер, а отображения $h,t \colon E \to V$ ставят в соответствие ребру его начало и соответственно конец. Два ребра $e,e' \in E$ называются последовательными, если $t(e)=h(e')$. Путь в графе – это слово над множеством $E$ его рёбер, в котором любые два соседних ребра являются последовательными; длина слова называется длиной пути. В частности, пустое слово над $E$ – это путь (длины 0), называемый пустым путём. Говорят, что путь начинается в начале его первого ребра и заканчивается в конце его последнего ребра. Условимся, что пустой путь может начинаться в любой вершине. Если путь начинается в вершине $v$ и заканчивается в вершине $v'$, мы называем его путём из $v$ в $v'$. Вершина $v'$ называется достижимой из вершины $v$, если существует путь из $v$ в $v'$. Теперь условие $|Q \operatorname{.} w|=1$ можно выразить следующим образом: слово $w$ – это последовательность меток, которые читаются в графе автомата подмножеств $\mathcal{P}(\mathscr{A})$ вдоль пути, который начинается в $Q$ и заканчивается одноэлементным подмножеством. Например, метки выделенного жирным шрифтом пути на рис. 11 образуют уже знакомое нам синхронизирующее слово автомата $\mathscr{C}_4$. При этом легко видеть, что более короткого пути из $Q=\{0,1,2,3\}$ в одноэлементное подмножество нет, и, значит, у $\mathscr{C}_4$ нет более короткого синхронизирующего слова, как и утверждалось при обсуждении примера 1.1. Таким образом, вопрос о том, синхронизируем ли данный ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$, сводится к следующему вопросу о достижимости в графе автомата подмножеств $\mathcal{P}(\mathscr{A})$: существует ли путь от $Q$ к одноэлементному подмножеству? Понятно, что наличие или отсутствие такого пути не зависит от меток рёбер, и потому последний вопрос в действительности касается носителя автомата $\mathcal{P}(\mathscr{A})$. Для решения задач достижимости в графах имеются стандартные методы, например поиск в ширину (см. [55; § 22.2]). Мы видим, что, применяя поиск в ширину к носителю автомата подмножеств, можно разрешить вопрос о синхронизируемости исходного автомата. Описанная процедура концептуально очень проста, но становится неэффективной с ростом числа состояний автомата, поскольку число множеств состояний растёт экспоненциально. Однако следующий критерий синхронизируемости (установленный независимо в пионерских работах Лю [117; теорема 15] и Черни [44; теорема 2] и многократно переоткрывавшийся) приводит к намного более эффективному алгоритму. Предложение 2.1. ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ синхронизируем тогда и только тогда, когда для любых $q,q'\in Q $ существует слово $w \in\Sigma^*$ такое, что $q \operatorname{.} w=q'\! \operatorname{.} w$. Доказательство. Конечно, в доказательстве нуждается только достаточность. Возьмём два произвольных состояния $q,q'\in Q $ и рассмотрим слово $w_1$ такое, что $q \operatorname{.} w_1=q'\! \operatorname{.} w_1$. Тогда $|Q \operatorname{.} w_1|<|Q|$. Если $|Q \operatorname{.} w_1|=1$, то $w_1$ синхронизирует $\mathscr{A}$. Если $|Q \operatorname{.} w_1|> 1$, возьмём два состояния $p,p'\in Q \operatorname{.} w_1$ и рассмотрим слово $w_2$ такое, что $p \operatorname{.} w_2=p'\! \operatorname{.} w_2$. Тогда $|Q \operatorname{.} w_1w_2| <|Q \operatorname{.} w_1|$. Если $|Q \operatorname{.} w_1w_2|=1$, то слово $w_1w_2$ синхронизирует $\mathscr{A}$; в противном случае мы продолжаем процесс. Ясно, что этот процесс приведёт к синхронизирующему слову для $\mathscr{A}$ за не более чем $|Q|-1$ шагов. Предложение доказано. Если $Q$ – конечное множество и $1\leqslant k\leqslant|Q|$, мы для краткости называем $k$-элементные подмножества в $Q$ его $k$-подмножествами. Множество всех $k$-подмножеств в $Q$ таких, что $1\leqslant k\leqslant m$ для некоторого $m\leqslant|Q|$, обозначим через $\mathcal{P}^{\leqslant m}(Q)$. Если $\mathscr{A}=\langle Q,\Sigma\rangle$ – ДКА, то $|P \operatorname{.} a|\leqslant|P|$ для любого подмножества $P\in\mathcal{P}(Q)$ и любой буквы $a\in\Sigma$. Поэтому для любого фиксированного $m\leqslant|Q|$ множество $\mathcal{P}^{\leqslant m}(Q)$ замкнуто относительно действия букв из $\Sigma$ и, следовательно, определяет подавтомат в автомате подмножеств. Этот подавтомат называется автоматом $m$-подмножеств ДКА $\mathscr{A}$ и обозначается $\mathcal{P}^{\leqslant m}(\mathscr{A})$. На рис. 12 изображён автомат 2-подмножеств автомата $\mathscr{C}_4$. Теперь предложение 2.1 можно переформулировать так. Следствие 2.1. ДКА $\mathscr{A}$ синхронизируем тогда и только тогда, когда для любого $2$-подмножества $D$ множества его состояний в носителе автомата $\mathcal{P}^{\leqslant2}(\mathscr{A})$ найдётся путь от $D$ к $1$-подмножеству. Как и выше, вопрос о синхронизируемости данного ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ сводится к вопросу о достижимости в некотором графе. Однако на сей раз мы имеем дело с носителем автомата $\mathcal{P}^{\leqslant2}(\mathscr{A})$, а этот граф имеет $\dfrac{|Q|(|Q|+1)}2$ вершин и $\dfrac{|Q|(|Q|+1)}2\,|\Sigma|$ рёбер. Известно, что поиск в ширину обрабатывает граф с $n$ вершинами и $m$ рёбрами за время $\Theta(n+m)$ (см., например, [55; § 22.2]). Поэтому основанный на следствии 2.1 алгоритм проверяет ДКА $\mathscr{A}$ на синхронизируемость за время $O(|Q|^2|\Sigma|)$. Будем называть этот алгоритм алгоритмом Лю–Черни в честь его первооткрывателей. Основываясь на глубоком анализе строения случайных автоматов, М. В. Берлинков предложил идею алгоритма для проверки синхронизируемости данного ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ за время $O(|Q|\,|\Sigma|)$ в среднем (см. [25; § 2] и [26; § 4]). Алгоритм состоит из набора тестов с ответами ДА/НЕТ. Подробное описание тестов дано в разделе второй статьи цикла, посвящённом синхронизации случайных автоматов; здесь же приведём три ключевых свойства набора:
П. С. Агеев [2] реализовал алгоритм Берлинкова в немного усовершенствованной редакции9. Эксперименты из [2] демонстрируют, что, начиная с ДКА с 31 состоянием, реализация алгоритма Берлинкова опережает реализацию алгоритма Лю–Черни по быстродействию и что с ростом числа состояний преимущество алгоритма Берлинкова возрастает. Дальнейшие обсуждения в разделе 2 предполагают знакомство читателя с основами теории сложности вычислений10, в частности со стандартными классами сложности $\mathbf{P}$, $\mathbf{NP}$, $\mathbf{PSPACE}$ и т. п. В рамках этой теории задача о проверке ДКА на синхронизируемость ставится как следующая задача распознавания:
DFA-SYNC: синхронизируемость полного детерминированного автомата.
Вход: полный детерминированный конечный автомат $\mathscr{A}$. Ответ: ДА, если $\mathscr{A}$ синхронизируем, НЕТ в противном случае. Следствие 2.1 сводит задачу DFA-SYNC к известной задаче достижимости в графах:
PATH: (ориентированная) достижимость в графе.
Вход: граф $\Gamma$ и две его вершины $s_0$ и $s_1$. Ответ: ДА, если в $\Gamma$ есть путь из $s_0$ в $s_1$, НЕТ в противном случае. Задача PATH – одна из “канонических” полных задач для класса сложности $\mathbf{NL}$, т. е. класса задач, разрешимых на недетерминированной машине Тьюринга с использованием $O(\log n)$ дополнительной памяти для входа длиной $n$ (см. [130; теорема 16.2]). Комбинируя следствие 2.1 и недетерминированный алгоритм для PATH, использующий логарифмическую дополнительную память, легко показать, что задача DFA-SYNC лежит в классе $\mathbf{NL}$. В действительности она, как и PATH, $\mathbf{NL}$-полна. Этот результат, полученный в 2010 г. индийским информатиком А. В. Сриджитом, ранее не публиковался. Мы приводим доказательство с любезного разрешения автора. Доказательство. Ясно, что достаточно L-свести к DFA-SYNC некоторую $\mathbf{NL}$-полную задачу. (L-сведе́ние – это сведе́ние, использующее логарифмическую дополнительную память.) Мы построим L-сведе́ние от сужения PATH на входы вида $(\Gamma,s_0,s_1)$, где $\Gamma$ – граф конфигураций недетерминированной машины Тьюринга, использующей $O(\log n)$ дополнительной памяти для входа длиной $n$, вершина $s_0$ отвечает начальной конфигурации машины на данном входе, а вершина $s_1$ – единственной принимающей конфигурации, в которой машина останавливается. Именно такие входы задачи PATH в действительности используются в доказательстве теоремы 16.2 в [130], поэтому состоящая из них подзадача $\mathbf{NL}$-полна. Произвольную недетерминированную машину Тьюринга можно за счёт введения новых состояний в количестве, логарифмическом от их исходного числа, превратить в машину, у которой из каждой конфигурации есть переход в не более чем две. Поэтому без ограничения общности можно считать, что в графе $\Gamma$ каждая вершина служит началом не более чем двух рёбер.
Итак, пусть $(\Gamma=\langle V,E,h,t\rangle,s_0,s_1)$ – вход указанной подзадачи. Добавляя к множеству $E$ петли в вершинах, в которых начинается меньше двух рёбер, модифицируем граф $\Gamma$ так, чтобы каждая вершина из $V$ служила началом ровно двух рёбер. (Скажем, оба ребра, начинающиеся в $s_1$, будут петлями.) Понятно, что на наличие/отсутствие пути из $s_0$ в $s_1$ такая модификация не влияет. Теперь пометим рёбра графа $\Gamma$ с помощью двух букв $a$ и $b$ так, чтобы для каждой вершины $v\in V$ одно из рёбер, начинающихся в $v$, имело метку $a$, а второе – метку $b$; в остальном выбор меток произволен. Получившийся помеченный граф представляет ДКА $\mathscr{G}:=\langle V,\{a,b\},\zeta\rangle$, в котором функция перехода $\zeta$ определяется метками: $\zeta(v,c)=v'$ для $c\in\{a,b\}$ и $v,v'\in V$ тогда и только тогда, когда ребро $v\to v'$ несёт метку $c$. Пусть $\overline{V}:=\{\overline{v}\mid v\in V\}$. Положим $Q:=V\cup\overline{V}$ и построим ДКА $\mathscr{A}(\Gamma):=\langle Q,\{0,1\},\delta\rangle$, определив функцию $\delta$ следующим образом:
$$
\begin{equation*}
\delta(v,0):=\overline{v},\quad \delta(v,1):=\zeta(v,a),\quad \delta(\overline{v},0):=\overline{s}_1,\quad \delta(\overline{v},1):=\zeta(v,b),
\end{equation*}
\notag
$$
для $v\in V\setminus\{s_1\}$ и
$$
\begin{equation*}
\delta(s_1,0)=\delta(s_1,1):=s_1,\quad \delta(\overline{s}_1,0):=\overline{s}_1,\quad \delta(\overline{s}_1,1):=s_0.
\end{equation*}
\notag
$$
Схема автомата $\mathscr{A}(\Gamma)$ приведена на рис. 13.
Ясно, что построение автомата $\mathscr{A}(\Gamma)$ по исходной тройке $(\Gamma,s_0,s_1)$ осуществимо с использованием логарифмической дополнительной памяти. Отметим ещё, что если определить кодирование $\chi\colon\{a,b\}\to\{0,1\}^+$ правилом $a\chi:=1$, $b\chi:=01$, то, как легко проверить, $\zeta(v,x)=\delta(v,x\chi)$ для любых $v\in V$ и $x\in\{a,b\}^*$. Утверждается, что в графе $\Gamma$ имеется путь из $s_0$ в $s_1$ тогда и только тогда, когда ДКА $\mathscr{A}(\Gamma)$ синхронизируем. Действительно, если такой путь есть и метки его рёбер в автомате $\mathscr{G}$ составляют слово $x\in\{a,b\}^+$, непосредственно проверяется, что слово $001\cdot x\chi$ синхронизирует $\mathscr{A}(\Gamma)$. Обратно, пусть ДКА $\mathscr{A}(\Gamma)$ синхронизируем. Поскольку $\delta(s_1,0)=\delta(s_1,1)=s_1$, любое слово из $\{0,1\}^*$ фиксирует состояние $s_1$, и потому синхронизирующее слово переводит $\mathscr{A}(\Gamma)$ именно в это состояние. В частности, есть слова $w\in\{0,1\}^+$ такие, что $\delta(s_0,w)=s_1$ (например, таково синхронизирующее слово). Возьмём кратчайшее слово $w$ с таким свойством. Путь из $s_0$ в $s_1$ в автомате $\mathscr{A}(\Gamma)$ вдоль $w$ не посещает состояние $s_0$ второй раз, а потому этот путь не заходит в состояние $\overline{s}_1$, из которого можно перейти только в $s_0$. Отсюда следует, что в $w$ не встречается блок 00, поскольку двукратное действие 0 переводит в $\overline{s}_1$ любое состояние, кроме $s_1$. Легко видеть, что слова над $\{0,1\}$, в которых отсутствует блок 00, лежат в образе $\chi$, и, значит, $w=x\chi$ для некоторого $x\in\{a,b\}^+$. Путь в $\mathscr{G}$ вдоль слова $x$ ведёт из $s_0$ в $s_1$. Предложение доказано. 2.2. Синхронизируемые автоматы и регулярные языки(Формальным) языком над данным конечным алфавитом $\Sigma$ называется любое подмножество в $\Sigma^*$. С помощью конечных автоматов выделяется весьма важный тип языков – регулярные языки; автоматы при этом выступают в роли распознавателей. Чтобы превратить ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ в распознаватель, достаточно выделить в множестве $Q$ состояние $q_0$, называемое начальным, и непустое подмножество $F$, состояния из которого называются заключительными. Распознаватель $(\mathscr{A},q_0,F)$ принимает слово $w\in\Sigma^*$, если $w$ – последовательность меток вдоль пути в $\mathscr{A}$, который начинается в состоянии $q_0$ и заканчивается в одном из состояний из $F$, т. е. если $q_0 \operatorname{.} w\in F$. Множество всех слов, принимаемых $(\mathscr{A},q_0,F)$, называется языком, распознаваемым автоматом $\mathscr{A}$. Регулярный язык в $\Sigma^*$ – это язык, распознаваемый каким-то ДКА с входным алфавитом $\Sigma$. Классическая теорема Клини [106] характеризует класс регулярных языков над $\Sigma$ как наименьший класс языков, который:
Напомним, что для синхронизируемого ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ через $\operatorname{Sync}\mathscr{A}$ обозначается множество всех его синхронизирующих слов. Конструкция автомата подмножеств из п. 2.1 позволяет легко доказать следующий факт. Предложение 2.3. $\operatorname{Sync}\mathscr{A}$ – регулярный язык для синхронизируемого ДКА $\mathscr{A}$. Доказательство. Пусть $\mathscr{A}=\langle Q,\Sigma\rangle$. Слово из $\Sigma^*$ синхронизирует $\mathscr{A}$ тогда и только тогда, когда помеченный им путь в автомате подмножеств $\mathcal{P}(\mathscr{A})$ ведёт из $Q$ в некоторое одноэлементное подмножество. Поэтому язык $\operatorname{Sync}\mathscr{A}$ распознаётся ДКА $\mathcal{P}(\mathscr{A})$, если в качестве начального состояния выбрать $Q$, а в качестве множества заключительных состояний – множество $\{\{q\}\mid q\in Q\}$. Предложение доказано. Напомним, что $\operatorname{Sync}\mathscr{A}$ – идеал моноида $\Sigma^*$ (лемма 1.1). С учётом этого, предложение 2.3 означает, что для любого синхронизируемого ДКА $\mathscr{A}$ язык $\operatorname{Sync}\mathscr{A}$ есть непустой регулярный идеал. Нетрудно видеть, что такая формулировка допускает обращение. Предложение 2.4. Для произвольного регулярного идеала $I$ моноида $\Sigma^*$ найдётся такой синхронизируемый автомат $\mathscr{A}$, что $I=\operatorname{Sync}\mathscr{A}$. Доказательство. Пусть $(\mathscr{A},q_0,F)$ – распознаватель для $I$ с наименьшим числом состояний. Тогда в $\mathscr{A}$ любое состояние $q$ достижимо из $q_0$, т. е. для $q$ найдётся такое слово $u\in\Sigma^*$, что $q_0 \operatorname{.} u=q$. (В противном случае мы получили бы распознаватель меньшего размера, отбросив недостижимые из $q_0$ состояния.) Поэтому в $\mathscr{A}$ все переходы из любого заключительного состояния $f\in F$ ведут в состояние из $F$: если слово $w\in\Sigma^*$ таково, что $q_0 \operatorname{.} w=f$, то $w\in I$ и для любой буквы $a\in\Sigma$ имеем $f \operatorname{.} a=(q_0 \operatorname{.} w) \operatorname{.} a=q_0 \operatorname{.} wa\in F$, поскольку $wa\in I$. Отсюда следует, что множество $F$ должно состоять из одного элемента, скажем, $s$ – иначе отождествление всех состояний из $F$ дало бы распознаватель меньшего размера. Для любого $w\in I$ и любого состояния $q$ имеем $q \operatorname{.} w=(q_0 \operatorname{.} u) \operatorname{.} w=q_0 \operatorname{.} uw\in F=\{s\}$, так как $uw\in I$. Поэтому любое слово из $I$ синхронизирует автомат $\mathscr{A}$ к $s$, т. е. $I\subseteq\operatorname{Sync}\mathscr{A}$. Обратное включение следует из того, что $s$ – единственное состояние, к которому можно синхронизировать $\mathscr{A}$, и потому любое слово из $\operatorname{Sync}\mathscr{A}$ обязано перевести $q_0$ в $s$. Предложение доказано. При $|\Sigma|\geqslant2$ произвольный регулярный идеал в $\Sigma^*$ можно реализовать как язык $\operatorname{Sync}\mathscr{A}$ для некоторого сильно связного синхронизируемого автомата $\mathscr{A}$ – это (уже весьма неочевидное) уточнение получено Рожериу Рейшем и Эмануеле Родаро [144]. В 2010-х гг. изучение взаимосвязей между синхронизируемыми автоматами и регулярными идеалами моноида $\Sigma^*$ развилось в довольно активное исследовательское направление в духе так называемой дескриптивной сложности (descriptional complexity) – теории, которая измеряет сложность объектов размерами их описаний. Непустые регулярные идеалы моноида $\Sigma^*$ – это бесконечные объекты, а синхронизируемые автоматы позволяют описать их в терминах конечных множеств, причём зачастую такое описание оказывается намного более компактным, чем “стандартное” описание с помощью распознавателей. Например, можно проверить, что любой ДКА, распознающий язык $\operatorname{Sync}\mathscr{C}_4$, где $\mathscr{C}_4$ – синхронизируемый ДКА с четырьмя состояниями из примера 1.1, имеет не менее 12 состояний. Среди публикаций в указанном направлении можно отметить [72], [88], [92], [93], [119]–[121], [139], [146]. Вернёмся теперь к вычислительной сложности распознавания синхронизируемости. Недавно обнаружилось (см. [66]), что эта сложность может существенно меняться при наложении простейших ограничений. В [66] систематически изучается семейство задач, параметризованное регулярными языками:
DFA-SYNC[$L$]: синхронизируемость ДКА при регулярном ограничении $L$.
Вход: полный детерминированный конечный автомат $\mathscr{A}$. Ответ: ДА, если $\mathscr{A}$ синхронизируем словом из $L$, НЕТ в противном случае. Рассмотренная в п. 2.1 задача DFA-SYNC входит в это семейство: она получается, когда в роли регулярного языка $L$ выступает язык всех слов над входным алфавитом автомата, что не накладывает никаких ограничений на строение синхронизирующих слов. На практике, однако, часто возникают ситуации, когда синхронизирующие слова обязаны иметь определённый формат. Так, если устройство, моделируемое автоматом, может функционировать в двух режимах – обычном и отладочном, то инструкции для отладки должны начинаться и заканчиваться специальной командой, которая сначала переключает устройство в отладочный режим, а затем возвращает его к обычной работе. (Пользователь $\mathrm{\TeX}$а наверняка вспомнит здесь про переключение $\mathrm{\TeX}$а в математический режим и обратно с помощью знака $\$ $.) Такое ограничение соответствует регулярному языку вида $a\Xi^*a$, где $a$ – выделенная специальная команда, а $\Xi$ – набор всех остальных команд устройства. Оказывается, что уже это естественное ограничение сразу делает задачу синхронизируемости вычислительно сложной. Предложение 2.5. Задача DFA-SYNC[$a\Xi^*a$], где $a\notin\Xi$, является $\mathbf{NP}$-полной при $|\Xi|=1$ и $\mathbf{PSPACE}$-полной при $|\Xi|>1$. В обоих случаях ($|\Xi|=1$ и $|\Xi|>1$) трудность задачи DFA-SYNC[$a\Xi^*a$] обеспечивается несложным сведе́нием от задачи FA-INTERSECTION, в которой дано конечное семейство распознавателей над алфавитом $\Xi$ и требуется определить, есть ли слово из $\Xi^*$, принимаемое всеми этими распознавателями. (Сведе́ние описано в доказательстве предложения 1 в [66].) Задача FA-INTERSECTION является $\mathbf{PSPACE}$-полной при $|\Xi|>1$ (см. [110]) и $\mathbf{NP}$-полной при $|\Xi|=1$ (см., например, [68]). В работе [66] показано, что для любого регулярного языка $L$ задача DFA-SYNC[$L$] лежит в классе $\mathbf{PSPACE}$; отсюда вытекает $\mathbf{PSPACE}$-полнота задачи DFA-SYNC[$a\Xi^*a$] при $|\Xi|>1$. В случае когда $\Xi$ состоит из одной буквы, скажем, $b$, принадлежность задачи DFA-SYNC[$a\Xi^*a$] классу $\mathbf{NP}$ не совсем очевидна, так как у синхронизируемого ДКА $\mathscr{A}=\langle Q,\{a,b\}\rangle$ может не быть синхронизирующих слов из $ab^*a$ полиномиальной от $|Q|$ длины. Однако в [66; предложение 1] проверено, что эта задача лежит в $\mathbf{NP}$. В [66] приведено много примеров регулярных языков $L$ над двух- и трёхбуквенными алфавитами, для которых задача DFA-SYNC[$L$] является $\mathbf{PSPACE}$- полной. Полная классификация таких языков пока остаётся открытой проблемой. Сложность синхронизации при различных регулярных ограничениях исследуется также в [91], [94]–[97]. 2.3. Сложность вычисления порога синхронизацииМинимум длин синхронизирующих слов синхронизируемого ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется его порогом синхронизации и обозначается $\operatorname{rt}(\mathscr{A})$. Для вычисления этого параметра может использоваться автомат подмножеств, поскольку $\operatorname{rt}(\mathscr{A})$ есть длина кратчайшего пути из $Q$ в одноэлементное множество в носителе автомата $\mathcal{P}(\mathscr{A})$. Конечно, в наихудшем случае для этого потребуется экспоненциальное от $|Q|$ время. Тем не менее попытки реализовать этот подход были (см., например, [102], [145], [179]). В отличие от ситуации с проверкой синхронизируемости переход к “полиномиальному” подавтомату 2-подмножеств здесь не помогает. Более того, при стандартных допущениях теории сложности вычислений можно показать, что вычисление порога синхронизации – труднорешаемая задача. Начнём анализ с обсуждения следующей задачи распознавания:
SHORT-SW: синхронизация словом данной длины.
Вход: ДКА $\mathscr{A}$ и натуральное число $\ell$. Ответ: ДА, если $\operatorname{rt}(\mathscr{A})\leqslant\ell$, НЕТ в противном случае. В формулировке задачи SHORT-SW не сказано, в какой форме – унарной или бинарной – записывается число $\ell$. Дело в том, что оба варианта данной задачи равноправны. (Это следует из того факта, что если ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ синхронизируем, то $\operatorname{rt}(\mathscr{A})<|Q|^3$; см. подробное обсуждение в п. 3.2 ниже.) И. К. Рысцов [150; теорема 3] доказал $\mathbf{NP}$-полноту задачи SHORT-SW. Как это нередко случалось в теории синхронизируемых автоматов, пионерская работа осталась незамеченной, и впоследствии этот важный результат неоднократно переоткрывался (см., например, [64], [82], [165]). Доказательство. Чтобы показать, что задача SHORT-SW лежит в классе $\mathbf{NP}$, сначала проверим, синхронизируем ли данный ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$. Как показано в п. 2.1, это можно сделать за полиномиальное от $|Q|$ время. Если $\mathscr{A}$ несинхронизируем, ответ на вход $(\mathscr{A},\ell)$ задачи SHORT-SW отрицателен. Если $\mathscr{A}$ синхронизируем, проверим неравенство $\ell\geqslant|Q|^3$; если оно выполнено, то ответ на вход $(\mathscr{A},\ell)$ положителен. Наконец, если $\ell<|Q|^3$, то недетерминированный алгоритм угадывает слово $w\in\Sigma^*$ длины $\leqslant\ell$, а затем проверяет, синхронизирует ли $w$ автомат $\mathscr{A}$. Такая проверка производится за время $\leqslant\ell|Q|$.
Для доказательства $\mathbf{NP}$-трудности используется сведе́ние от классической $\mathbf{NP}$-полной задачи SAT (см. [130; теорема 8.2]). Напомним, что вход SAT – это система клозов (дизъюнкций литералов, т. е. булевых переменных и их отрицаний), а на выходе требуется определить, существует ли набор значений переменных, обращающий все клозы системы в истинные высказывания. Для произвольного входа $\psi$ задачи SAT с $n$ переменными $x_1,\dots,x_n$ и $m$ клозами $c_1,\dots,c_m$ построим ДКА $\mathscr{A}(\psi):=\langle Q,\{a,b\}\rangle$ следующим образом. Множество $Q$ состоит из $(n+1)m$ символов $q_{i,j}$, где $1\leqslant i\leqslant m$, $1\leqslant j\leqslant n+1$, и особого символа $z$. Действие букв определяется правилами:
$$
\begin{equation*}
\begin{alignedat}{2} &q_{i,j} \operatorname{.} a :=\begin{cases} z, &\text{если литерал $x_j$ входит в клоз $c_i$},\\ q_{i,j+1} &\text{в противном случае}, \end{cases} &&\quad 1 \leqslant i \leqslant m,\quad 1 \leqslant j \leqslant n; \\ &q_{i,j} \operatorname{.} b :=\begin{cases} z, &\text{если литерал $\neg x_j$ входит в клоз $c_i$},\\ q_{i,j+1} &\text{в противном случае}, \end{cases} &&\quad 1 \leqslant i \leqslant m,\quad 1 \leqslant j \leqslant n; \\ &q_{i,n+1} \operatorname{.} a=q_{i,n+1} \operatorname{.} b=z \operatorname{.} a=z \operatorname{.} b:=z, &&\quad 1\leqslant i\leqslant m. \end{alignedat}
\end{equation*}
\notag
$$
На рис. 14 изображены два автомата вида $\mathcal{A}(\psi)$, построенных для двух систем клозов:
$$
\begin{equation*}
\begin{aligned} \, \psi_1&=\{c_1:=x_1 \vee x_2 \vee x_3,\, c_2:=\neg x_1 \vee x_2,\, c_3=\neg x_2\vee x_3,\,c_4:=\neg x_2 \vee \neg x_3\}, \\ \psi_2&=\{c_1:=x_1 \vee x_2,\, c_2:=\neg x_1 \vee x_2,\, c_3=\neg x_2\vee x_3,\,c_4:=\neg x_2 \vee \neg x_3\}. \end{aligned}
\end{equation*}
\notag
$$
Каждая “строчка” на рис. 14 помечена соответствующим клозом, а каждый “столбик” – соответствующей переменной. Если из состояния $q \in Q$ на рис. 14 не исходит ребро с меткой $c \in \{a,b\}$, то подразумевается ребро $q \xrightarrow{c} z$ (все такие рёбра опущены на рисунке, чтобы не загромождать его). Системы $\psi_1$ и $\psi_2$ различаются только первым клозом: в $\psi_1$ этот клоз содержит литерал $x_3$, а в первом клозе $\psi_2$ такого литерала нет. Соответственно, автоматы $\mathscr{A}(\psi_1)$ и $\mathscr{A}(\psi_2)$ отличаются только исходящим ребром с меткой $a$ в состоянии $q_{1,3}$: в $\mathscr{A}(\psi_1)$ это ребро ведёт в $z$ (и потому не изображено на рис. 14), а в $\mathscr{A}(\psi_2)$ оно ведёт в состояние $q_{1,4}$ (и показано пунктиром). Заметим, что набор значений истинности $x_1=x_2:=0$, $x_3:=1$ выполняет все клозы из $\psi_1$, в то время как система клозов $\psi_2$ невыполнима. Нетрудно проверить, что слово $bba$ синхронизирует $\mathcal{A}(\psi_1)$, в то время как $\mathcal{A}(\psi_2)$ не синхронизируется никаким словом длины 3 (но синхронизируется любым словом над $\{a,b\}$ длины 4). В общем случае легко проверить, что ДКА $\mathscr{A}(\psi)$ синхронизируется любым словом над $\{a,b\}$ длины $n+1$ и синхронизируется словом длины $n$ тогда и только тогда, когда система $\psi$ выполнима. Таким образом, если произвольному входу $\psi$ задачи SAT поставить в соответствие вход $(\mathscr{A}(\psi),n)$ задачи SHORT-SW, где $n$ – число переменных в $\psi$, то получим полиномиальное сведе́ние от SAT к SHORT-SW. Предложение доказано. Введём задачу перечисления, соответствующую SHORT-SW:
#SHORT-SW: перечисление синхронизирующих слов данной длины.
Вход: ДКА $\mathscr{A}$ и натуральное число $\ell$. Ответ: число синхронизирующих слов длины $\ell$ для $\mathscr{A}$. Сведе́ние из доказательства предложения 2.6 устанавливает взаимно однозначное соответствие между выполняющими наборами значений переменных для системы клозов $\psi$ от $n$ переменных и синхронизирующими словами длины $n$ для ДКА $\mathscr{A}(\psi)$. В частности, число выполняющих наборов для $\psi$ равно числу синхронизирующих слов длины $n$ для $\mathscr{A}(\psi)$, т. е. построенное сведе́ние экономно (parsimonious) в смысле теории сложности перечислений. Поэтому его можно рассматривать как сведе́ние задачи #SAT (задача перечисления выполняющих наборов для данной системы клозов) к задаче #SHORT-SW. Поскольку задача #SAT является $\#\mathbf{P}$-полной (см. [130; теорема 18.1]), получаем, что задача #SHORT-SW является $\#\mathbf{P}$-трудной. С другой стороны, легко видеть, что #SHORT-SW лежит в классе $\#\mathbf{P}$. В итоге получается следующий факт, впервые явно отмеченный, по-видимому, Йоргом Ольшевским и Михаэлем Уммельсом [129; замечание 3]. В литературе довольно часто можно встретить утверждения типа “задача нахождения длины кратчайшего синхронизирующего слова $\mathbf{NP}$-полна” или даже “задача нахождения кратчайшего синхронизирующего слова $\mathbf{NP}$-полна”; при этом подразумевается результат предложения 2.6. Конечно, такая интерпретация предложения 2.6 некорректна; более того, конструкция из доказательства этого предложения позволяет заключить, что принадлежность упомянутых задач классу $\mathbf{NP}$ несовместима со стандартными допущениями теории сложности вычислений. Чтобы продемонстрировать это, введём соответствующую задачу распознавания:
SHORTEST-SW: равенство порога синхронизации данному числу.
Вход: ДКА $\mathscr{A}$ и натуральное число $\ell$. Ответ: ДА, если $\operatorname{rt}(\mathscr{A})=\ell$, НЕТ в противном случае. Поставим в соответствие произвольной системе клозов $\psi$ от $n$ переменных вход $(\mathscr{A}(\psi),n+1)$ задачи SHORTEST-SW. Как отмечено в доказательстве предложения 2.6, ДКА $\mathscr{A}(\psi)$ синхронизируется любым словом над $\{a,b\}$ длины $n+1$ и синхронизируется словом длины $n$ тогда и только тогда, когда система $\psi$ выполнима. Поэтому $\operatorname{rt}(\mathscr{A}(\psi))=n+1$ тогда и только тогда, когда система $\psi$ невыполнима. Получаем сведение к SHORTEST-SW от отрицания SAT, т. е. от $\mathbf{coNP}$-полной задачи. Следовательно, задача SHORTEST-SW является $\mathbf{coNP}$-трудной. Поэтому принадлежность SHORTEST-SW классу $\mathbf{NP}$ имело бы следствием равенство $\mathbf{NP}=\mathbf{coNP}$, которое считается маловероятным. Если же принять гипотезу $\mathbf{NP}\ne\mathbf{coNP}$, то SHORTEST-SW не лежит в $\mathbf{NP}$, что означает, что даже недетерминированный алгоритм не может определить порог синхронизации данного ДКА за полиномиальное время от размера этого ДКА. Класс сложности, для которого SHORTEST-SW служит полной задачей, нашли Павел Гавриховский [73] и, независимо от него, Ольшевски и Уммельс [129; теорема 1]. Нужным классом оказался класс $\mathbf{DP}$ (Difference Polynomial-Time), введённый Христосом Пападимитриу и Михалисом Яннакакисом [131] (см. также [130; § 17.1]). Он состоит из всех задач $Z$, допускающих полиномиальное сведе́ние к паре задач $Z_+$ и $Z_-$ из $\mathbf{NP}$, при котором входы задачи $Z$ с ответом ДА преобразуются в точности в пары вида (вход $Z_+$ с ответом ДА, вход $Z_-$ с ответом НЕТ). $\mathbf{DP}$ – обширный класс, который включает объединение $\mathbf{NP}\cup\mathbf{coNP}$, и предполагается, что включение – строгое. Типичной $\mathbf{DP}$-полной задачей является задача SAT-UNSAT, в которой для пары систем клозов $\psi$, $\varphi$ нужно узнать, верно ли, что $\psi$ выполнима, а $\varphi$ невыполнима. С помощью сведе́ния от SAT-UNSAT в [73] и [129] доказано следующее утверждение. Теперь локализуем задачу нахождения порога синхронизации. Она ставится так:
COMPUTE-RT: нахождение порога синхронизации.
Вход: синхронизируемый ДКА $\mathscr{A}$. Ответ: величина $\operatorname{rt}(\mathscr{A})$. Отличие COMPUTE-RT от SHORTEST-SW состоит в том, что мы напрямую ищем порог синхронизации, а не проверяем его равенство заранее заданному числу. Функциональный класс сложности $\mathbf{FP}^{\mathbf{NP}[\log]}$ состоит из всех функций, вычислимых за полиномиальное время на детерминированной машине Тьюринга, которая может обращаться к оракулу для $\mathbf{NP}$-полной задачи, причём число запросов есть логарифмическая функция от размера входных данных (см. [130; § 17.1]). Легко понять, что функция $\mathscr{A}\mapsto\operatorname{rt}(\mathscr{A})$ лежит в этом классе. Действительно, уже отмечалось, что если ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ синхронизируем, то $\operatorname{rt}(\mathscr{A})<|Q|^3$. Поэтому с помощью двоичного поиска можно найти $\operatorname{rt}(\mathscr{A})$, запрашивая оракул для $\mathbf{NP}$-полной задачи SHORT-SW $O(\log|Q|)$ раз. Как доказали Ольшевски и Уммельс [129; теорема 4], эта очевидная верхняя оценка на сложность задачи COMPUTE-RT точна. Доказательство основано на сведе́нии от задачи MAX-SAT, $\mathbf{FP}^{\mathbf{NP}[\log]}$-полнота которой установлена в [111]. (В задаче MAX-SAT для данной системы клозов требуется найти максимальное число одновременно выполнимых клозов.) Наконец, обсудим нахождение синхронизирующего слова минимальной длины:
COMPUTE-SW: нахождение синхронизирующего слова минимальной длины.
Вход: синхронизируемый ДКА $\mathscr{A}$. Ответ: синхронизирующее слово минимальной длины для $\operatorname{rt}(\mathscr{A})$. Понятно, что найти само синхронизирующее слово минимальной длины не легче, чем найти его длину, т. е. порог синхронизации. Поэтому из предложения 2.8 следует, что задача COMPUTE-SW является $\mathbf{FP}^{\mathbf{NP}[\log]}$-трудной. С другой стороны, несложно проверить, что синхронизирующее слово минимальной длины для ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ можно вычислить за полиномиальное от $|Q|$ время на детерминированной машине Тьюринга, если разрешить запросы к оракулу для следующей $\mathbf{NP}$-полной задачи (см. [129; теорема 5]):
SHORT-SUBSET-SW: синхронизация подмножества словом данной длины.
Вход: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$, подмножество $S\subseteq Q$ и число $\ell$ в унарной записи. Ответ: ДА, если существует такое слово $w\in\Sigma^*$, что $|S \operatorname{.} w|=1$ и $|w|\leqslant\ell$, НЕТ в противном случае. $\mathbf{NP}$-трудность задачи SHORT-SUBSET-SW следует из предложения 2.6, поскольку задача SHORT-SW является её частным случаем (при $S=Q$), а принадлежность SHORT-SUBSET-SW классу $\mathbf{NP}$ очевидна11. Класс всех функций, вычислимых за полиномиальное от размера входа время на детерминированной машине Тьюринга, использующей оракул для $\mathbf{NP}$-полной задачи, обозначается через $\mathbf{FP}^{\mathbf{NP}}$; этот класс важен для теории сложности вычислений как “место прописки” задачи коммивояжёра (см. [130; теорема 17.5]). Предполагается, что класс $\mathbf{FP}^{\mathbf{NP}}$ строго больше класса $\mathbf{FP}^{\mathbf{NP}[\log]}$. Итак, сложность задачи COMPUTE-SW ограничена классом $\mathbf{FP}^{\mathbf{NP}[\log]}$ снизу и классом $\mathbf{FP}^{\mathbf{NP}}$ сверху. Пока неизвестно, полна ли эта задача для какого-либо встречавшегося в литературе функционального класса сложности. Упомянем ещё работы [67], [191], в которых задача SHORT-SW исследуется в рамках популярной сейчас параметрической теории сложности. В них были рассмотрены все наиболее естественные для входов $(\mathscr{A}=\langle Q,\Sigma\rangle,\ell)$ задачи SHORT-SW параметры – размер множества состояний $Q$, размер алфавита $\Sigma$ и число $\ell$, а также их комбинации. 2.4. Сложность аппроксимации порога синхронизацииПоскольку точное значение порога синхронизации трудновычислимо, естественно задаться вопросом о существовании полиномиальных приближённых алгоритмов. Оказалось, что в предположении, что $\mathbf{P}\ne\mathbf{NP}$, для любого полиномиально вычислимого приближения к порогу синхронизации найдутся серии автоматов, на которых эти приближения дают большую относительную погрешность. Этот факт установили Павел Гавриховский и Дамиан Страшак [74]; он перекрывает все предшествующие результаты о трудноаппроксимируемости порога синхронизации (см. [24], [25], [75]). Дадим необходимые для обсуждений определения. Полиномиальным алгоритмом для аппроксимации порога синхронизации назовем произвольный алгоритм $U$, который для каждого синхронизируемого автомата $\mathscr{A}$ за полиномиальное от числа его состояний время возвращает натуральное число $U(\mathscr{A})\geqslant\operatorname{rt}(\mathscr{A})$. Пусть $f\colon\mathbb{N}\to\mathbb{R}$ – некоторая функция. Будем говорить, что $U$ аппроксимирует порог синхронизации с точностью до $f(n)$, если для любого $n\in\mathbb{N}$ и любого синхронизируемого автомата $\mathscr{A}$ с $n$ состояниями верно неравенство
$$
\begin{equation*}
\frac{U(\mathscr{A})}{\operatorname{rt}(\mathscr{A})}\leqslant f(n).
\end{equation*}
\notag
$$
Предложение 2.9 [74; теорема 16]. Пусть $\epsilon>0$. Если $\mathbf{P}\ne\mathbf{NP}$, то никакой полиномиальный алгоритм не аппроксимирует порог синхронизации с точностью до $n^{1-\epsilon}$. Доказательство предложения 2.9 задействует мощные методы современной теории сложности вычислений, в частности полученную Дэвидом Цукерманом [193] дерандомизацию классического результата Йохана Хостада [90] о трудноаппроксимируемости задачи о максимальной клике. Результат предложения 2.9 неулучшаем: существуют полиномиальные алгоритмы, которые аппроксимирует порог синхронизации с точностью до $n$. Так, Майкл Гербуш и Брент Хиринга [75] построили для каждого фиксированного целого $k\geqslant 2$ алгоритм, который, получив на вход синхронизируемый автомат синхронизации $\ell$, находит его синхронизирующее слово длины не более $\lceil(n-1)/(k-1)\rceil\ell$ за время $O(kmn^k+n^4/k)$. Другими словами, такой алгоритм аппроксимирует порог синхронизации с точностью до $\lceil(n-1)/(k-1)\rceil$; в частности, при $k=2$ получаем аппроксимацию с точностью до $n-1$. Алгоритмы из [75] получены модификацией жадного сжимающего алгоритма, который подробно обсуждается в п. 3.2 ниже (см. там алгоритм 1). Д. С. Ананичев и В. В. Гусев [8] показали, что верхняя оценка точности $\lceil(n-1)/(k-1)\rceil$ не может быть улучшена в рамках очень широкого семейства полиномиальных алгоритмов для аппроксимации порога синхронизации; это семейство включает алгоритмы из [75]. 3. Гипотеза Черни3.1. Гипотеза Черни: формулировка и немного историиДля краткости будем называть ДКА с $n$ состояниями $n$-автоматом. В 1964 г. Черни [44] указал серию синхронизируемых $n$-автоматов с порогом синхронизации $(n-1)^2$. Серия Черни состоит из автоматов $\mathscr{C}_n=\langle\{0,1,\dots,n-1\},\{a,b\}\rangle$, где буквы $a$ и $b$ действуют следующим образом:
$$
\begin{equation*}
i \operatorname{.} a:=\begin{cases} i, &\text{если}\ i>0, \\ 1,&\text{если}\ i=0; \end{cases}\qquad i \operatorname{.} b=i+1\!\!\!\!\pmod{n}.
\end{equation*}
\notag
$$
Наш первый пример синхронизируемого автомата (см. пример 1.1 и рис. 1) – это 4-автомат из серии Черни; $n$-автомат $\mathscr{C}_n$ изображён слева на рис. 15. Серия $\{\mathscr{C}_n\}_ {n=2,3,\dots}$ многократно переоткрывалась (см., например, [64], [69], [71], [114]). Легко видеть, что слово $(ab^{n-1})^{n-2}a$ длины $n(n-2)+1=(n-1)^2$ синхронизирует автомат $\mathscr{C}_n$ к состоянию 1. Предложение 3.1 [44; лемма 1]. Порог синхронизации автомата $\mathscr{C}_n$ равен $(n-1)^2$. Есть несколько изящных доказательств этого результата. Доказательство из [13], представленное ниже, основано на прозрачной идее и увязывает автоматы из серии Черни с экстремальной серией графов из классической работы Хельмута Виландта [192]. Доказательство предложения 3.1. Достаточно показать, что если $w$ – синхронизирующее слово минимальной длины для $\mathscr{C}_n$, то $|w|\geqslant(n-1)^2$. Поскольку буква $b$ действует на $Q$ как циклическая перестановка, слово $w$ не может заканчиваться на $b$. (В противном случае удаление последней буквы дало бы более короткое синхронизирующее слово.) Таким образом, $w=w'a$, причём префикс $w'$ таков, что $Q \operatorname{.} w'=\{0,1\}$.
Буква $a$ фиксирует каждое состояние в своем образе $\{1,2,\dots,n-1\}$, и потому за каждым вхождением $a$ в $w$, кроме последнего, следует вхождение $b$. (В противном случае в $w$ встретились бы два вхождения буквы $a$ подряд и, удалив одно из этих вхождений, мы получили бы более короткое синхронизирующее слово.) Поэтому если положить $c:=ab$, то слово $w'$ можно переписать в слово $v$ над алфавитом $\{b,c\}$. Действия $b$ и $c$ индуцируют новый ДКА на множестве состояний $Q$; обозначим этот индуцированный ДКА (изображённый на рис. 15 справа) через $\mathscr{W}_n$. Поскольку слова $w'$ и $v$ действуют на $Q$ одинаково, слово $vc$ синхронизирует автомат $\mathscr{W}_n$ к состоянию 2. По лемме 1.1 для произвольного $u\in\{b,c\}^*$ слово $uvc$ также синхронизирует автомат $\mathscr{W}_n$ к состоянию 2. Следовательно, для каждого $\ell \geqslant |vc|$ существует путь длины $\ell$ в $\mathscr{W}_n$ из любого заданного состояния $i$ в 2. В частности, полагая $i=2$, мы заключаем, что для каждого $\ell \geqslant |vc|$ существует цикл длины $\ell$ в $\mathscr{W}_n$. Носитель автомата $\mathscr{W}_n$ имеет простые циклы только двух длин: $n$ и $n- 1$. Каждый цикл в $\mathscr{W}_n$ должен состоять из простых циклов этих двух длин, поэтому каждое число $\ell \geqslant |vc|$ должно выражаться как комбинация $n$ и $n-1$ с неотрицательными целыми коэффициентами. Напомним следующий хорошо известный элементарный результат из теории чисел. Лемма 3.1 [142; теорема 2.1.1]. Если натуральные числа $k_1$ и $k_2$ взаимно просты, то $k_1k_2-k_1-k_2$ – это наибольшее натуральное число, которое не представимо в виде комбинации $k_1$ и $k_2$ с неотрицательными целыми коэффициентами. Лемма 3.1 влечёт, что $|vc|>n(n-1)-n-(n-1)=n^2-3n+1$. Допустим, что $|vc|=n^2-3n+2$. Тогда имеется путь такой длины из состояния 1 в состояние 2. В ДКА $\mathscr{W}_n$ любое ребро с началом 1 имеет концом 2, и потому в этом пути за ним должен следовать цикл длины $n^2-3n+1$. По лемме 3.1 циклов такой длины не существует. Следовательно, $|vc|\geqslant n^2-3n+3$. Действие буквы $b$ на любом множестве состояний $S\subseteq Q$ не может изменить мощность $S$, а действие буквы $c$ может уменьшить её не более чем на 1. Поэтому слово $vc$ должно содержать не менее $n-1$ вхождений буквы $c$. Следовательно, длина слова $v$ над $\{b,c\}$ не менее $n^2-3n+2$, и $v$ содержит не менее $n-2$ вхождений буквы $c$. Поскольку каждое вхождение $c$ в $v$ соответствует вхождению фактора $ab$ в $w'$, мы заключаем, что длина $w'$ над $\{a,b\}$ не меньше $n^2-3n+2+n-2=n^2-2n$. Таким образом, $|w|=|w'a|\geqslant n^2-2n+1=(n-1)^2$. Предложение 3.1 доказано. Определим функцию Черни $\mathfrak{C}(n)$ как максимум порогов синхронизации синхронизируемых $n$-автоматов. Предложение 3.1 даёт неравенство $\mathfrak{C}(n)\geqslant(n-1)^2$. Гипотеза Черни утверждает, что имеет место равенство $\mathfrak{C}(n)=(n-1)^2$. Гипотеза Черни. Любой синхронизируемый ДКА с $n$ состояниями синхронизируется словом длины $(n-1)^2$. В обширной литературе по гипотезе Черни и связанным с ней вопросам обычно ссылаются на работу Черни [44] как на источник гипотезы. Эта основополагающая статья примечательна во многих отношениях, но гипотеза не была сформулирована в ней. Понятно, что на самом деле мало кто читал статью [44] в словацком оригинале, но сейчас опубликован в открытом доступе её авторизованный английский перевод. Поэтому заинтересованный читатель может убедиться, что Черни ограничивается наблюдением [44; теорема 3], которое в наших обозначениях записывается как и заключает статью следующим осторожным выводом:“Между нижней и верхней оценками имеется значительное расхождение, и их необходимо сделать более точными. Можно ожидать, что это будет возможным, в особенности для верхней оценки”. Представляется, что гипотеза впервые появилась в печати в 1966 г. в заметке Петера Штарке [170]. Штарке улучшил верхнюю оценку в (3) до величины $1+n(n-1)(n-2)/2$, что стало первой полиномиальной верхней оценкой для $\mathfrak{C}(n)$, и завершил [170] замечанием, которое мы воспроизводим с использованием наших обозначений: “Данное Черни доказательство утверждения (3) в [44] подсказывает гипотезу о том, что $\mathfrak{C}(n)=(n-1)^2$ выполняется для любого $n\geqslant1$. К сожалению, попытки доказать или опровергнуть эту гипотезу оказались безуспешными”. К этой цитате можно добавить, что ситуация, констатированная в её последней фразе, сохраняется12 уже 56 лет! Известно, что Черни обсуждал синхронизируемые автоматы (используя термин “directable”) и гипотезу о длине их синхронизирующих слов на нескольких чехословацких конференциях, состоявшихся во второй половине 1960-х гг. Некоторые авторы относят гипотезу Черни к его сообщению на Братиславской конференции по кибернетике в 1969 г. Первая публикация Черни [45] (совместная с Алисой Пирицкой и Бланкой Розенауеровой), в которой явно упоминалась гипотеза, появилась в 1971 г. С учётом этого думается, что имя “Гипотеза Черни–Штарке” было бы более справедливым с исторической точки зрения, однако сейчас уже поздно менять терминологию, которая используется более сорока лет13. Возвращаясь к оценке вклада Штарке, упомянем ещё его монографию [171], в § I.9 которой обсуждаются результаты из [44] и [170]. Эта книга сыграла важную роль в привлечении внимания исследователей к синхронизируемым автоматам. 3.2. Верхние оценки. Оценка Пэна–ФранкляДо недавнего времени лучшей верхней оценкой для функции Черни была оценка $\mathfrak{C}(n)\leqslant(n^3-n)/6$. Для произвольного синхронизируемого $n$-автомата синхронизирующее слово длины не больше $(n^3-n)/6$ может быть получено c помощью следующего алгоритма.  Алгоритм 1 ищет синхронизирующее слово “сверху вниз”, придерживаясь жадной стратегии: он пытается сжать текущее множество кратчайшим возможным словом. (Мы говорим, что слово $u\in\Sigma^*$ сжимает подмножество $S\subseteq Q$ в ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$, если $|S \operatorname{.} u|<|S|$.) Оценим время работы алгоритма и длину возвращаемого им слова. Если $|Q|=n$, то основной цикл алгоритма 1 выполняется не более $n-1$ раз, так как после каждого прохождения цикла размер текущего множества $P$ уменьшается по крайней мере на 1. Слово $v$ в строке 7 – это последовательность меток кратчайшего пути из 2-подмножества множества $P$ в 1-подмножество множества $Q$ в автомате $\mathcal{P}^{\leqslant2}(\mathscr{A})$ (см. следствие 2.1 и обсуждение алгоритма Лю–Черни в п. 2.1). Поиск в ширину находит такой путь за время $O(n^2|\Sigma|)$. Таким образом, время работы алгоритма 1 полиномиально зависит от размеров ДКА $\mathscr{A}$. Детальный временной анализ алгоритма 1 проделал Дэвид Эппштейн в [64; теорема 5]; он показал, что за счёт предвычисления длин путей в автомате $\mathcal{P}^{\leqslant2}(\mathscr{A})$ алгоритм 1 можно исполнить за время $O(n^3+n^2|\Sigma|)$. Статья [64], которая содержит и ряд других важных результатов, получила широкую известность, благодаря чему на алгоритм 1 и его варианты часто ссылаются как на алгоритм Эппштейна. Сам Эппштейн в [64] указывает на работу Натараджана [126] как на источник алгоритма, а фактически алгоритм появился на 20 лет раньше, ещё в заметке Штарке [170], с которой ни Натараджан, ни Эппштейн не были знакомы. Чтобы оценить длину возвращаемого алгоритмом 1 слова $w$, оценим длины слов $v$, дописываемых к $w$ при каждом прохождении основного цикла. Рассмотрим типичный шаг, на котором $|P|=k>1$, и пусть $v=a_1\cdots a_\ell$, где $a_1,\dots,a_\ell\in\Sigma$. Тогда по выбору $v$ каждое из множеств
$$
\begin{equation}
P_1:=P,\quad P_2:=P_1.a_1,\quad\dotsc,\quad P_\ell:=P_{\ell-1} \operatorname{.} a_{\ell-1}
\end{equation}
\tag{4}
$$
содержит ровно $k$ состояний. Поскольку $|P_{\ell} \operatorname{.} a_{\ell}|=|P \operatorname{.} v|<|P|=|P_\ell|$, найдутся два различных состояния $p_\ell,p'_\ell\in P_\ell$ такие, что $p_{\ell} \operatorname{.} a_{\ell}=p'_{\ell} \operatorname{.} a_{\ell}$. Положим $R_\ell:=\{p_\ell,p'_\ell\}$ и для всех $i=1,\dots,\ell-1$ определим 2-подмножества $R_i:=\{p_i,p'_i\}\subseteq P_i$, выбирая элементы $p_i$, $p'_i$ так, чтобы выполнялись равенства $p_i. a_i=p_{i+1}$, $p'_i. a_i=p'_{i+1}$ (см. рис. 16). Если $R_i\subseteq P_j$ для каких-то $j<i$, то для слова $a_1\cdots a_ja_i\cdots a_\ell$ длины $j+(\ell-i)<\ell$ выполняется неравенство $|P \operatorname{.} a_1\cdots a_ja_i\cdots a_\ell|<|P|$, что противоречит выбору $v$ как кратчайшего слова со свойством $|P \operatorname{.} v|<|P|$. Поэтому $R_i\nsubseteq P_j$ при всех $i$, $j$ таких, что $1\leqslant j<i\leqslant\ell$. Пусть $k>1$. Последовательность $k$-подмножеств $P_1,P_2,\dots$ некоторого множества назовём 2-обновляемой, если каждое множество $P_i$ содержит “новое” 2-подмножество, т. е. такое 2-подмножество $R_i$, что $R_i\nsubseteq P_j$ для всех $j<i$. Аргумент, приведённый сейчас, доказывает следующее утверждение. Лемма 3.2. Пусть $\mathscr{A}=\langle Q,\Sigma\rangle$ – ДКА, $P$ – подмножество в $Q$ с $|P|=k> 1$, а $v=a_1\cdots a_\ell$, где $a_1,\dots,a_\ell\in\Sigma$, – кратчайшее слово со свойством $|P. v|<|P|$. Тогда последовательность $k$-подмножеств (4) является 2-обновляемой. В силу леммы 3.2, чтобы оценить сверху длину слова $v$ для $\mathscr{A}=\langle Q,\Sigma\rangle$ с $|Q|=n$, достаточно найти максимум длин 2-обновляемых последовательностей $k$-подмножеств в $n$-множестве как функцию от $n$ и $k$. Это – нетривиальная задача из комбинаторики конечных множеств. Легко построить пример 2-обновляемой последовательности $k$-подмножеств длины $\binom{n-k+2}2$: нужно зафиксировать какие-то $k-2$ элемента данного $n$-множества и поочерёдно добавлять к ним 2-подмножества, выбранные из оставшихся $n-k+2$ элементов. Но будет ли так построенная последовательность максимальной по длине, далеко не очевидно. Указанную задачу решил Петер Франкль [70], подтвердивший оптимальность только что описанной конструкции14. Предложение 3.2. Максимальная длина $2$-обновляемой последовательности $k$-подмножеств в $n$-множестве равна $\binom{n-k+2}2$. Доказательство. Каждому $k$-подмножеству $I=\{i_1,\dots,i_k\}$ множества $\{1,2,\dots,n\}$ поставим в соответствие следующий многочлен $D(I)$ от переменных $x_{i_1},\dots,x_{i_k}$ над полем $\mathbb{R}$:
$$
\begin{equation*}
I=\{i_1,\dots,i_k\}\mapsto D(I):=\begin{vmatrix} 1 & i_1 & i_1^2 & \dots & i_1^{k-3} & x_{i_1} & x_{i_1}^2 \\ 1 & i_2 & i_2^2 & \dots & i_2^{k-3} & x_{i_2} & x_{i_2}^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 1 & i_k & i_k^2 & \dots & i_k^{k-3} & x_{i_k} & x_{i_k}^2 \end{vmatrix}_{k\times k}.
\end{equation*}
\notag
$$
Допустим, что $k$-подмножества $P_1,\dots,P_\ell$ образуют $2$-обновляемую последовательность, а многочлены $D(P_1),\dots,D(P_\ell)$ линейно зависимы над $\mathbb{R}$. В этом случае некоторый многочлен $D(P_j)$ будет линейной комбинацией многочленов $D(P_1),\dots,D(P_{j-1})$. По определению $2$-обновляемой последовательности в $P_j$ есть такие элементы $p$, $p'$, что $\{p,p'\}\nsubseteq P_i$ для всех $i<j$. Если положить $x_p=p$, $x_{p'}=p'$ и $x_t=0$ при $t\ne p,p'$ в каждом из многочленов $D(P_1),\dots,D(P_j)$, то многочлены $D(P_1),\dots,D(P_{j-1})$ обратятся в 0, поскольку в каждом из получившихся определителей два последних столбца пропорциональны. Обратится в 0 и любая линейная комбинация этих многочленов. С другой стороны, многочлен $D(P_j)$ при указанных значениях переменных отличен от 0, так как равен произведению некоторого определителя Вандермонда размера $(k-2)\times(k-2)$ и определителя $\begin{vmatrix} p & p^2\\ p' & (p')^2\end{vmatrix}=pp'(p'-p)$. Поэтому многочлен $D(P_j)$ не может быть линейной комбинацией многочленов $D(P_1),\dots,D(P_{j-1})$. Противоречие.
Итак, многочлены, построенные по $k$-подмножествам из $2$-обновляемой последовательности, линейно независимы, а значит, длина такой последовательности не превосходит размерности линейного пространства $L$, натянутого на все многочлены вида $D(I)$. Покажем, что эта размерность не превосходит $\binom{n-k+2}2$. Пусть $W=\{1,2,\dots,k-2\}$. Рассмотрим все $k$-подмножества $T_1,\dots,T_s$ в $\{1,2,\dots,n\}$, которые можно получить, добавив к $W$ некоторое 2-подмножество из $\{k-1,k,\dots,n\}$; ясно, что $s=\binom{n-k+2}2$. Докажем, что многочлены $D(T_1),\dots,D(T_s)$ порождают пространство $L$, что даст требуемую оценку сверху на размерность $L$. Для этого индукцией по числу элементов в $I\setminus W$ покажем, что для всякого $k$-подмножества $I$ в $\{1,2,\dots,n\}$ многочлен $D(I)$ линейно выражается через $D(T_1),\dots,D(T_s)$. Если $|I\setminus W|=2$, то $I$ – это одно из подмножеств $T_i$. Тогда $D(I)=D(T_i)$ и всё ясно. Если $|I\setminus W|>2$, то найдётся элемент $i_0\in W\setminus I$. Существует такой многочлен $p(x)=\alpha_0+\alpha_1x+\alpha_2x^2+\cdots+\alpha_{k-3}x^{k-3}$ над $\mathbb{R}$, что $p(i_0)=1$ и $p(i)=0$ для всех $i\in W\setminus\{i_0\}$. Пусть $I=\{i_1,\dots,i_k\}$, а $I'=I\cup\{i_0\}$. Определитель
$$
\begin{equation*}
\begin{vmatrix} p(i_0) & 1 & i_0 & i_0^2 & \dots & i_0^{k-3} & x_{i_0} & x_{i_0}^2 \\ p(i_1) & 1 & i_1 & i_1^2 & \dots & i_1^{k-3} & x_{i_1} & x_{i_1}^2 \\ p(i_2) & 1 & i_2 & i_2^2 & \dots & i_2^{k-3} & x_{i_2} & x_{i_2}^2 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ p(i_k) & 1 & i_k & i_k^2 & \dots & i_k^{k-3} & x_{i_k} & x_{i_k}^2 \end{vmatrix}_{(k+1)\times (k+1)}
\end{equation*}
\notag
$$
равен 0, так как его первый столбец есть линейная комбинация следующих $k-2$ столбцов с коэффициентами $\alpha_0,\alpha_1,\alpha_2,\dots,\alpha_{k-3}$. Раскрыв этот определитель по первому столбцу, получим равенство Поскольку $p(i_0)=1$ и $I'\setminus\{i_0\}=I$, это равенство можно переписать так:
$$
\begin{equation}
D(I)=\sum_{j=1}^{k}(-1)^{j+1}p(i_j)D(I'\setminus\{i_j\}).
\end{equation}
\tag{5}
$$
Поскольку $p(i)=0$ для всех $i\in W\setminus\{i_0\}$, в правой части равенства (5) ненулевые коэффициенты будут лишь у таких многочленов $D(I'\setminus\{i_j\})$, что $i_j\notin W$. Множество $I'\setminus\{i_j\}$ получено из $I$ заменой элемента $i_j\notin W$ на элемент $i_0\in W\setminus I$, и, значит, у $I'\setminus\{i_j\}$ больше общих элементов с $W$, чем у $I$. Поэтому и по предположению индукции любой многочлен $D(I'\setminus\{i_j\})$ с $i_j\notin W$ есть линейная комбинация многочленов $D(T_1),\dots,D(T_s)$. В силу (5) то же верно и для $D(I)$. Предложение доказано. Комбинируя лемму 3.2 и предложение 3.2, получаем следующее утверждение. Следствие 3.1. Пусть $\mathscr{A}=\langle Q,\Sigma\rangle$ – ДКА, $P$ – подмножество в $Q$ с $|P|=k> 1$, а $v\in\Sigma^*$ – кратчайшее слово со свойством $|P \operatorname{.} v|<|P|$. Тогда справедливо неравенство $|v|\leqslant\binom{n-k+2}2$. Итак, если $\ell_k$ – длина слова, которое алгоритм 1 приписывает к текущему слову после шага, на котором текущее множество содержит $k$ состояний, следствие 3.1 гарантирует, что $\ell_k\leqslant\binom{n-k+2}2$. Используя тождество $\binom{m}2+\binom{m}3=\binom{m+1}3$, легко вычислить
$$
\begin{equation}
\sum_{k=2}^n\begin{pmatrix} n-k+2 \\ 2\end{pmatrix}= \begin{pmatrix} n+1 \\ 3\end{pmatrix}=\frac{n^3-n}{6}
\end{equation}
\tag{6}
$$
(см., например, [83; формула (5.10)]). Поэтому, суммируя все неравенства $\ell_k \leqslant \binom{n-k+2}2$ от $k=2$ до $k=n$, приходим к анонсированной выше оценке В литературе неравенство (7) обычно называют оценкой Пэна–Франкля, ссылаясь на статьи Жана-Эрика Пэна [135] и Франкля [70]. Пэн доказал лемму 3.2 и предположил оценку $\binom{n-k+2}2$ для максимальной длины 2-обновляемой последовательности в своём докладе на коллоквиуме по теории графов и комбинаторике в Марселе в 1981 г.; статья [135] основана на этом докладе. Франкль узнал о предположении Пэна – и немедленно доказал его – во время другого коллоквиума по комбинаторике, проходившего в Билефельде в ноябре 1981 г. Для полноты картины добавим, что впервые оценка (7) возникла в статье Мартина Фишлера и Мейера Танненбаума [69], поданной на симпозиум по теории переключательных схем и автоматов, проходивший в Санта-Монике, Калифорния, в октябре 1970 г. В [69] эта оценка выводится из комбинаторной гипотезы, эквивалентной предположению Пэна; Фишлер и Танненбаум приводят несколько частных случаев, в которых им удалось доказать гипотезу, и выражают надежду, что смогут представить полное доказательство на симпозиуме. Однако, по всей видимости, эта надежда не оправдалась – никаких следов доказательства в дальнейших публикациях я не обнаружил. Затем оценка (7) была переоткрыта Зви Кохави и Джозефом Виноградом [108], [109], но её обоснование в этих статьях содержало неисправимые ошибки. В 1987 г. как лемма 3.2, так и предложение 3.2 были ещё раз переоткрыты А. А. Клячко, И. К. Рысцовым и М. А. Спиваком [107], которые были знакомы с работами [69], [108], [109], но не знали про существование статей Пэна и Франкля. Приведённое выше доказательство предложения 3.2 взято из работы15 [107]; доказательство из [70] использует ту же идею. Слово, возвращаемое алгоритмом 1, не всегда будет кратчайшим синхронизирующим словом для данного ДКА. Это неудивительно, поскольку, как уже отмечалось в п. 2.3, никакой полиномиальный алгоритм, даже недетерминированный, не может вычислить порог синхронизации для произвольного синхронизируемого ДКА16. Конкретным примером может служить ДКА $\mathscr{C}_{4}$. На этом автомате алгоритм 1 возвращает слово $ab^2abab^3a$ длины 10, складывающееся из меток выделенного жирным шрифтом пути на рис. 17. Как мы знаем, это слово не является кратчайшим синхронизирующим словом для $\mathscr{C}_{4}$. Здесь проявляется одна из основных трудностей проблемы синхронизации – неприменимость стандартных подходов к оптимизации: оптимальное решение не обязано вести себя оптимально на промежуточных этапах. Для $\mathscr{C}_{4}$ оптимальным решением является слово $ab^3ab^3a$, но его нельзя найти с помощью алгоритма 1, поскольку на втором шаге алгоритм выбирает кратчайшее слово, сжимающее 3-подмножество $\{1,2,3\}$, т. е. слово $b^2a$, в то время как правильным выбором было бы более длинное слово $b^3a$ (ср. с рис. 11). За свою “поспешность” алгоритм расплачивается на следующем шаге, так как попадает в 2-подмножество $\{1,3\}$, не сжимаемое никаким словом длины меньше 6. В литературе делались разного рода попытки усовершенствовать алгоритм 1, разрешая ему “заглядывать вперёд” и выбирать на каждом шаге не кратчайшее слово, сжимающее $k$-подмножество, а слово, которое оптимизирует какой-нибудь другой разумный параметр (см., например, [75] и обсуждение в [148; § 5]). Такие подходы представляют практический интерес, но, конечно, не могут преодолеть теоретический барьер, установленный результатами из п. 2.3. Разрыв между порогом синхронизации ДКА и длиной синхронизирующего слова, возвращаемого алгоритмом 1 на этом ДКА, может быть сколь угодно большим. Например, можно подсчитать, что для $n$-автомата $\mathscr{C}_{n}$ из серии Черни, порог синхронизации которого равен $(n-1)^2$ (см. предложение 3.1), алгоритм 1 возвращает слово длины $\Omega(n^2\log n)$. Алгоритм 1 попадает в семейство алгоритмов, аппроксимационные свойства которых исследовались Ананичевым и Гусевым в [8]. Из [8] можно извлечь примеры серий $n$-автоматов, на которых относительная погрешность алгоритма 1 составляет $\Omega(n)$. Поведение алгоритма 1 в среднем с теоретической точки зрения ещё совсем не изучено; на практике он демонстрирует вполне приемлемые результаты. Завершая обсуждение оценки Пэна–Франкля (7), отметим ещё, что для $n=1,2,3$ она даёт такие же значения, как и нижняя оценка $(n-1)^2$, поэтому эти три значения (0, 1 и 4 соответственно) точны. Пэн [135] проверил, что для любого синхронизируемого ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ с четырьмя и более состояниями найдётся слово $u\in\Sigma^*$ длины 9, действие которого сжимает множество $Q$ на три или более состояния: $|Q \operatorname{.} u|\leqslant|Q|-3$; новое доказательство этого факта дано в [57]. Если начать алгоритм 1 с $w:=u$ и $P:=Q \operatorname{.} u$, то сумма трёх последних слагаемых $\displaystyle\binom42+\displaystyle\binom32+\displaystyle\binom22=6+3+1$ в сумме $\displaystyle\sum_{k=2}^n\displaystyle\binom{n-k+2}2$ из (6) заменится на 9, что уменьшит сумму на 1. Поэтому для $n\geqslant4$ оценку (7) можно улучшить до Оценка (8) точна при $n=4$.3.3. Верхние оценки. Недавние продвиженияНа протяжении 35 лет оценка Пэна–Франкля оставалась лучшей верхней оценкой для порога синхронизации автоматов с данным числом состояний. В 2011 г. А. Н. Трахтман [183] опубликовал оценку $\mathfrak{C}(n)\leqslant n(7n^2+6n-16)/48$, доказательство которой, однако, содержало неустранимую ошибку. Тем не менее работа [183] содержала свежую идею, на основе которой Марек Шикула [177] получил оценку
$$
\begin{equation}
\mathfrak{C}(n)\leqslant\frac{85059n^3+90024n^2+196504n-10648}{511104}\,.
\end{equation}
\tag{9}
$$
Оценка Шикулы улучшает старший коэффициент $1/6=0.166666\ldots$ из оценки Пэна–Франкля до $\displaystyle\frac{85059}{511104}=\displaystyle\frac{28353}{170368}=0.166422\ldots$ . Наименьшее $n$, при котором выражение в правой части (9) оказывается меньше, чем $\dfrac{n^3-n}{6}$ , равно 724. Тем не менее, хотя с практической точки зрения полученное улучшение и незначительно, на фоне многолетнего “застоя” результат Шикулы воспринимается как существенное продвижение. В конце статьи [177] было высказано предположение, что оценка (9) может быть улучшена за счёт более аккуратных вычислений. Это предположение вскоре было подтверждено в заметке Я. Н. Шитова [168], где выведена оценка
$$
\begin{equation}
\mathfrak{C}(n)\leqslant\biggl(\frac{7}{48}+ \frac{15625}{798768}\biggr)n^3+o(n^3)
\end{equation}
\tag{10}
$$
со старшим коэффициентом приблизительно $0.1654$. Для детального обсуждения идеи из [183] и её реализации в [168], [177] потребуются некоторые определения и предварительные результаты. Пусть дан ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$. Будем говорить, что слово $w\in\Sigma^*$ избегает состояние $q\in Q$, если $q\notin Q \operatorname{.} w$. Состояние, для которого существует избегающее слово, называется избегаемым. Отметим, что если ДКА $\mathscr{A}$ синхронизируем и слово $v$ синхронизирует его к состоянию $s$, то $v$ избегает все состояния, кроме $s$. Поэтому в синхронизируемых автоматах все состояния, кроме, быть может, одного, избегаемы. Неизбегаемым в синхронизируемом ДКА может быть только такое состояние $z$, что $z \operatorname{.} a=z$ для каждой буквы $a\in\Sigma$. Будем называть такие состояния нулевыми, а ДКА, в котором есть нулевое состояние, – автоматом с нулём. Ясно, что в синхронизируемом ДКА может быть не больше одного нулевого состояния. Более того, в рассмотрениях, связанных с гипотезой Черни, можно ограничиться автоматами, в которых нет нулевых состояний. Это следует из двух наблюдений: во-первых, задача установления верхней границы для порога синхронизации $n$-автоматов сводится к двум частным случаям: случаю сильно связных автоматов и случаю автоматов с нулём; во-вторых, случай автоматов с нулём оказывается несложным. Сведе́ние из первого наблюдения – часть фольклора теории синхронизируемых автоматов. Следуя [188], оформим его в удобном для последующих ссылок виде. Лемма 3.3 [188; предложение 2.1]. Пусть $\mathbf{C}$ – класс ДКА, замкнутый относительно взятия подавтоматов и факторавтоматов, $\mathbf{C}_n$ – класс всех $n$-автоматов из $\mathbf{C}$, а $f\colon\mathbb{Z}^+\to\mathbb{N}$ – произвольная функция такая, что Если у каждого сильно связного синхронизируемого ДКА из $\mathbf{C}_n$ и каждого синхронизируемого ДКА с нулём из $\mathbf{C}_n$ порог синхронизации не превышает $f(n)$, то это же верно для всех синхронизируемых ДКА из $\mathbf{C}_n$. Доказательство. Пусть $\mathscr{A}=\langle Q,\Sigma\rangle$ – синхронизируемый ДКА из $\mathbf{C}_n$. Рассмотрим множество $S$ всех состояний, к которым его можно синхронизировать, и положим $m:=|S|$. Пусть $q\in S$ и $w\in\Sigma^*$ – слово, которое синхронизирует $\mathscr{A}$ к $q$. Тогда для любой буквы $a\in\Sigma$ слово $wa$ синхронизирует $\mathscr{A}$ к состоянию $q \operatorname{.} a$, откуда следует, что $q \operatorname{.} a\in S$. Поэтому ограничение функции переходов автомата $\mathscr{A}$ на множество $S\times\Sigma$ индуцирует подавтомат $\mathscr{S}$ с множеством состояний $S$. Очевидно, что ДКА $\mathscr{S}$ синхронизируем и сильно связен, а поскольку класс $\mathbf{C}$ замкнут относительно взятия подавтоматов, имеем $\mathscr{S}\in\mathbf{C}_m$. Следовательно, $\operatorname{rt}(\mathscr{S})\leqslant f(m)$. Пусть $v$ – синхронизирующее слово длины $f(m)$ для $\mathscr{S}$.
Рассмотрим теперь разбиение $\pi$ множества $Q$ на $S$ и $n-m$ одноэлементных классов. Легко видеть, что $\pi$ – конгруэнция автомата $\mathscr{A}$. Факторавтомат $\mathscr{A}/\pi$ синхронизируем, и класс $S$ является его нулевым состоянием. Поскольку класс $\mathbf{C}$ замкнут относительно взятия факторавтоматов, $\mathscr{A}/\pi\in\mathbf{C}_{n-m+1}$. Следовательно, $\operatorname{rt}(\mathscr{A}/\pi)\leqslant f(n-m+1)$. Пусть $u$ – синхронизирующее слово длины $f(n-m+1)$ для $\mathscr{A}/\pi$. Тогда $Q \operatorname{.} u\subseteq S$ и $S \operatorname{.} v$ – одноэлементное множество. Имеем $Q \operatorname{.} uv\subseteq S \operatorname{.} v$, и, значит, слово $uv$ синхронизирует $\mathscr{A}$. При этом согласно (11). Следовательно, $\operatorname{rt}(\mathscr{A})\leqslant f(n)$. Лемма доказана.Функция $(n-1)^2$ удовлетворяет неравенству (11). Поэтому, применяя лемму 3.3 к классу всех ДКА, получаем, что для доказательства гипотезы Черни её достаточно проверить для сильно связных синхронизируемых ДКА и для синхронизируемых ДКА с нулём. Давно известно ([149; теорема 1], см. также [157; теорема 6.1]), что для синхронизируемых ДКА с нулём гипотеза Черни верна; более того, для порога синхронизации синхронизируемых ДКА с нулём имеется лучшая, чем $(n-1)^2$, верхняя оценка. Предложение 3.3. Порог синхронизации синхронизируемого $n$-автомата с нулём не превышает $n(n-1)/2$, и эта оценка точна. Доказательство. Пусть $\mathscr{A}=\langle Q,\Sigma\rangle$ – синхронизируемый $n$-автомат с нулевым состоянием $z$. Ясно, что любое синхронизирующее слово синхронизирует $\mathscr{A}$ именно к $z$, поэтому из любого состояния $q\in Q$ есть путь в $z$. Для любого подмножества $S\subseteq Q\setminus\{z\}$ в кратчайшем пути, который начинается в каком-то состоянии из $S$ и заканчивается в $z$, все состояния, кроме первого, лежат в $Q\setminus S$ и никакое состояние не встречается дважды. Поэтому длина такого пути не превосходит $|Q\setminus S|=n-|S|$. Теперь построим синхронизирующее слово $w$ по следующему алгоритму:
инициализация: инициализируем $w$ пустым словом $\varepsilon$; цикл: до тех пор, пока $Q \operatorname{.} w\ne\{z\}$, находим кратчайший путь из $Q \operatorname{.} w\setminus\{z\}$ в $z$ и дописываем к $w$ слово, составленное из меток этого пути. После каждого прохождения цикла число состояний в $Q \operatorname{.} w$ становится меньше по крайней мере на 1, поэтому цикл исполняется не более $n-1$ раз. Как пояснено выше, длина слова, дописываемого к $w$ при $k$-м прохождении цикла, не превосходит
$$
\begin{equation*}
n-|Q \operatorname{.} w\setminus\{z\}|=n+1-|Q \operatorname{.} w|\leqslant n+1-(n-k+1)=k
\end{equation*}
\notag
$$
для каждого $k=1,\dots,n-1$. Отсюда следует, что Итак, $\operatorname{rt}(\mathscr{A})\leqslant n(n-1)/2$.
Чтобы доказать точность оценки, рассмотрим ДКА $\mathscr{R}_n:\!=\!\langle\{0,1,\dots,n- 1\},\Sigma\rangle$, в котором $\Sigma:=\{a_1,\dots,a_{n-1}\}$. Действие букв понятно из рис. 18: буква $a_1$ фиксирует все состояния, кроме 1, которое она переводит в 0, а буква $a_i$ при $2\leqslant i\leqslant n-1$ фиксирует все состояния, кроме $i-1$ и $i$, которые она переставляет. Эта серия автоматов указана И. К. Рысцовым [149; теорема 2] (см. также [157; теорема 6.1]). Видно, что $\mathscr{R}_n$ есть $n$-автомат, в котором 0 – нулевое состояние. Поскольку любое состояние можно перевести в 0, автомат $\mathscr{R}_n$ синхронизируем. Проверим, что $\operatorname{rt}(\mathscr{R}_n)\geqslant n(n-1)/2$. Пусть $w$ – синхронизирующее слово для $\mathscr{R}_n$. Для $S=\{s_1,\dots,s_t\}\subseteq Q$ положим $f(S):=\displaystyle\sum_{i=1}^t s_i$. Тогда $f(\{0\})=0$ и $f(Q)=n(n-1)/2$. Для любого $S$ и любой буквы $a_j$ имеем $f(S \operatorname{.} a_j)\geqslant f(S)-1$, поскольку каждая буква либо переставляет два соседних состояния, либо переводит $1$ и $0$ в $0$. С учётом того, что $Q \operatorname{.} w=\{0\}$, получаем
$$
\begin{equation*}
0=f(\{0\})=f(Q \operatorname{.} w)\geqslant f(Q)-|w|=\frac{n(n-1)}{2}-|w|,
\end{equation*}
\notag
$$
откуда следует, что $|w|\geqslant n(n-1)/2$. Предложение доказано. Размер алфавита в автоматах с нулём из серии $\mathscr{R}_n$, демонстрирующей точность оценки из предложения 3.3, растёт вместе с числом состояний. Можно ли достичь того же значения порога синхронизации на сериях автоматов с нулём над фиксированным алфавитом? Этот вопрос естествен сам по себе и, кроме того, тесно связан с одной важной задачей теории формальных языков (так называемой гипотезой Рестиво, см. обсуждение в [43; § 5]). Пока что ответ на него неизвестен; все встречающиеся в литературе “медленно синхронизируемые” серии $n$-автоматов с нулём над фиксированным алфавитом имеют порог синхронизации вида $n^2/4+O(n)$, т. е. примерно вдвое меньший, чем у серии $\mathscr{R}_n$ (см. [118], [138]). На данный момент дальше всех в этом вопросе продвинулись Д. С. Ананичев и Войтех Ворел [14]: для каждого $n\equiv4\pmod{12}$ начиная с $n=16$ они сконструировали синхронизируемый $n$-автомат с нулём и двумя входными буквами, порог синхронизации которого равен $n^2/4+2n-9$. Подытожим: лемма 3.3 и предложение 3.3 показывают, что улучшать оценку Пэна–Франкля достаточно для сильно связных автоматов. До конца п. 3.3 будем предполагать, что $\mathscr{A}=\langle Q,\Sigma\rangle$ – сильно связный синхронизируемый $n$-автомат. Тогда в $\mathscr{A}$ любое состояние избегаемо. В [183; лемма 3] утверждается, что для любого состояния в $\mathscr{A}$ найдётся избегающее слово длины не больше $n$. Это утверждение неверно; мы приведём контрпример чуть позже. Дальнейшие рассуждения из [183] в целом корректны. Их идея состоит в том, что можно сжать $Q$ наполовину, используя избегающие слова следующим образом. Пусть $v\in\Sigma^*$ таково, что размер подмножества $S:=Q \operatorname{.} v$ больше $n/2$. Тогда по принципу Дирихле существует состояние $p\in S$, для которого есть ровно одно состояние $q$ со свойством $p=q \operatorname{.} v$. Если слово $u$ избегает $q$, то по определению $q\notin Q \operatorname{.} u$, откуда следует, что $p\notin Q \operatorname{.} uv\subset Q \operatorname{.} v=S$. Поэтому $|Q \operatorname{.} uv|<|S|$. (Отметим здесь отличие от алгоритма 1: избегающие слова не дописываются справа, а “предписываются” слева.) Мы приходим к следующему алгоритму.  Обозначим слово, возвращаемое алгоритмом 2, через $w_{1/2}$. По построению для него выполнено неравенство $|Q \operatorname{.} w_{1/2}|\leqslant n/2$. Чтобы достроить $w_{1/2}$ до синхронизирующего слова, запустим со слова $w:=w_{1/2}$ и подмножества $P:=Q \operatorname{.} w_{1/2}$ алгоритм 1. При этом в силу следствия 3.1 к $w_{1/2}$ будет дописано слово длины не больше
$$
\begin{equation*}
\begin{aligned} \, \sum_{k=2}^{\lfloor n/2\rfloor}\begin{pmatrix} n-k+2 \\ 2\end{pmatrix}&= \sum_{k=2}^n\begin{pmatrix} n-k+2 \\ 2\end{pmatrix}- \sum_{k=\lfloor n/2\rfloor+1}^{n}\begin{pmatrix} n-k+2 \\ 2\end{pmatrix} \\ &=\begin{pmatrix} n+1 \\ 3\end{pmatrix}- \begin{pmatrix}\lceil n/2\rceil+2 \\ 3\end{pmatrix}. \end{aligned}
\end{equation*}
\notag
$$
(Сумма $\displaystyle\sum_{k=2}^n\binom{n-k+2}2$ указана в (6), а сумма $\displaystyle\sum_{k=\lfloor n/2\rfloor+1}^{n}\binom{n-k+2}2$ вычисляется тем же методом.) Элементарные подсчёты показывают, что
$$
\begin{equation*}
\begin{pmatrix} n+1 \\ 3\end{pmatrix}- \begin{pmatrix} \lceil n/2\rceil+2 \\ 3\end{pmatrix}=\begin{cases} \dfrac{n(7n^2-6n-16)}{48}&\text{при чётном}\ n, \\ \dfrac{7n^3-9n^2-31n-15}{48}&\text{при нечётном}\ n. \end{cases}
\end{equation*}
\notag
$$
Очевидно, что $7n^3-6n^2-16n>7n^3-9n^2-31n-15$ при всех натуральных $n$, поэтому можно выбрать $n(7n^2-6n-16)/48$ в качестве годной для любого $n$ верхней оценки длины слова, дописанного к $w_{1/2}$ алгоритмом 1. Итак, комбинация алгоритмов 2 и 1 позволяет строить синхронизирующие слова длины не больше (Теперь читателю должно стать понятней происхождение слагаемого $7/48$ в коэффициенте при $n^3$ в оценке (10).) Ясно, что улучшить оценку Пэна–Франкля с помощью только что описанного построения можно только при наличии хорошей верхней оценки для длины слова $w_{1/2}$. Поскольку оно собирается из избегающих слов, вопрос сводится к оценке их длины. Мы уже отмечали, что оценка, заявленная в [183], неверна. Приведём обещанный контрпример; он предложен в [81]. Автомат $\mathscr{E}_4$, изображённый на рис. 19, сильно связен, синхронизируем (словом $ab^2abab^2a$, например) и имеет четыре состояния. Однако можно проверить, что кратчайшее слово, избегающее состояние 0, – это слово $abbaba$ длины 6. Что же можно сказать о длине избегающих слов? Для удобства обсуждений введём термин порог избегаемости и обозначение $\operatorname{at}(\mathscr{A})$ для максимума длин кратчайших слов, избегающих состояния сильно связного синхронизируемого ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$:
$$
\begin{equation*}
\operatorname{at}(\mathscr{A}):=\max_{q\in Q}\{|w_q|\mid w_q\text{ - кратчайшее слово над $\Sigma$, избегающее $q$}\}.
\end{equation*}
\notag
$$
Легко видеть, что $\operatorname{at}(\mathscr{A})\leqslant\operatorname{rt}(\mathscr{A})+1$. Действительно, если $w$ – кратчайшее синхронизирующее слово для $\mathscr{A}$, то $w$ избегает все состояния, кроме состояния $s$, к которому оно синхронизирует $\mathscr{A}$. Поскольку $\mathscr{A}$ сильно связен, $s$ не является нулевым состоянием, т. е. $s \operatorname{.} a\ne s$ для некоторой буквы $a\in\Sigma$. Поэтому слово $wa$ длины $\operatorname{rt}(\mathscr{A})+1$ избегает $s$. Понятно, что оценка $\operatorname{at}(\mathscr{A})\leqslant\operatorname{rt}(\mathscr{A})+1$ не представляет интереса с точки зрения описанного выше подхода. Вопрос о существовании линейной по $n$ верхней оценки порога избегаемости в явном виде поставлен в [81]; пока он остаётся открытым. Основываясь на экспериментальных данных, Анджей Кисилевич, Якуб Ковальский и Марек Шикула выдвинули следующее предположение. Гипотеза ККШ [103; гипотеза 5]. Порог избегаемости любого сильно связного синхронизируемого автомата с $n$ состояниями не превышает $2n-2$. Предполагается, что гипотетическая верхняя оценка $2n-2$ точна для $n$-автоматов с тремя входными буквами при $n\geqslant4$ (см. [103]). В диссертации Ворела [190; теорема 3.26] для любого $n\geqslant5$ указан сильно связный синхронизируемый $n$-автомат с двумя входными буквами и порогом избегаемости $2n-3$. Заметим, что если линейная оценка порога избегаемости существует, то длина слова $w_{1/2}$, возвращаемого алгоритмом 2, оценивается сверху квадратичной функцией от $n$. Действительно, основной цикл алгоритма 2 выполняется не более $\lceil n/2\rceil$ раз, так как каждое прохождение цикла уменьшает размер текущего множества по крайней мере на 1. Следовательно, $w_{1/2}$ собирается из не более чем $\lceil n/2\rceil$ избегающих слов. При квадратичной верхней оценке на $|w_{1/2}|$ выражение (12) даёт оценку вида $(7/48)n^3+O(n^2)$ для порога синхронизации сильно связных синхронизируемых $n$-автоматов. Пока, однако, лучшая из известных верхних оценок порога избегаемости даётся выражением $n^2-3n+4$ (см. [177]). Такая оценка не позволяет ограничить длину слова, возвращаемого алгоритмом 2, настолько, чтобы улучшить оценку Пэна–Франкля через выражение (12). Поэтому в [177] слово, сжимающее автомат наполовину, строится более хитроумным способом. Он опирается на следующее ключевое соображение. Лемма 3.4 [177; лемма 2]. Пусть $\mathscr{B}=\langle R,\Sigma\rangle$ – произвольный ДКА, $S$ – непустое подмножество в $R$, а $T$ – непустое собственное подмножество в $S$. Если $T\nsubseteq S \operatorname{.} u$ для некоторого $u\in\Sigma^*$, то существует слово $v\in\Sigma^*$ длины не больше $|R|-|T|$ такое, что либо $|S \operatorname{.} v|<|S|$, либо $T\nsubseteq S \operatorname{.} v$. Объясним на идейном уровне, как работает лемма 3.4, отсылая к [177] за (довольно громоздкими) техническими деталями. Пусть, как и выше, $\mathscr{A}=\langle Q,\Sigma\rangle$ – сильно связный синхронизируемый $n$-автомат. Допустим, что уже построен некий фрагмент $w$ искомого “уполовинивающего” слова и множество $S:=Q \operatorname{.} w$ содержит $k$ состояний, где $n/2<k<n$. Если $u$ – слово, которое синхронизирует $\mathscr{A}$ к состоянию из $Q\setminus S$, то $q\notin S \operatorname{.} u$ для любого $q\in S$. Поэтому условия леммы 3.4 выполняются для любой пары множеств $S$ и $T:=\{q\}$, где $q\in S$. Применяя лемму ко всем таким парам множеств, получаем, что либо (случай 1) существует слово $v\in\Sigma^*$ длины не больше $n-1$ такое, что $|S \operatorname{.} v|<|S|$, либо (случай 2) для каждого состояния $q\in S$ найдётся слово $v_q$ длины не больше $n-1$ такое, что $q\notin S. v_q$. В случае 1 множество $S$ сжато словом линейной по $n$ длины (а не квадратичной, как при применении следствия 3.1). В случае 2 слово $wv_q$ избегает состояние $q\in S$, а слово $w$ избегает каждое состояние из $Q\setminus S$. Поэтому порог избегаемости ДКА $\mathscr{A}$ не превышает $|w|+n-1$. Теперь понятно, как лемма 3.4 может помочь построить слово, сжимающее $\mathscr{A}$ наполовину и более короткое, чем $w_{1/2}$. Если в процессе сжатия случай 2 произойдёт рано, когда длина построенного фрагмента $w$ ещё мала, получается сильная верхняя оценка на $\operatorname{at}(\mathscr{A})$, которую можно использовать для дальнейшего сжатия методом алгоритма 2. Если же случай 2 впервые случится поздно, т. е. при $k$, близком к $n/2$, это значит, что автомат сжат до $k$ состояний словом длины не больше $(n-k)(n-1)$. В действительности приведённые соображения ещё недостаточны, чтобы улучшить оценку Пэна–Франкля, – можно подсчитать, что если строить сжимающее наполовину слово, опираясь только на них, получится слово длины $n^3/16+O(n^2)$. Нам же нужно слово, в выражении для длины которого коэффициент при $n^3$ строго меньше $1/6-7/48=1/48$. (Здесь $1/6$ и $7/48$ – коэффициенты при $n^3$ в оценке Пэна–Франкля и соответственно в оценке длины слова, которое “дожимает” автомат c $\lfloor n/2\rfloor$ состояний до одного состояния.) К счастью, применяя лемму 3.4 во всей её общности и используя некоторые дополнительные ухищрения, построить такое слово удаётся. Улучшение оценки (9) до (10), достигнутое в [168], опирается на некоторое уточнение леммы 3.4. Отметим, что явный вид слагаемого $o(n^3)$ из (10) в [168] не указан; сказано только, что с помощью прямых вычислений можно довести оценку этого слагаемого до $O(n^2\log n)$. Поэтому, хотя оценка (10) асимптотически лучше, чем (9), пока неясно, на автоматах каких размеров начинается её преимущество. В [177] показано, что слово, синхронизирующее данный синхронизируемый $n$-автомат и имеющее длину не больше можно найти за полиномиальное от $n$ время. По-видимому, то же верно и для синхронизирующих слов, строящихся в [168], хотя в последней работе это не отмечено явно.Подводя итоги, можно констатировать, что идея сжатия с помощью избегающих слов сдвинула задачу о пороге синхронизации $n$-автоматов с мёртвой точки и в то же время породила новые задачи о синхронизируемых автоматах. Однако эта идея недостаточна для доказательства гипотезы Черни и даже для получения оценки вида $o(n^3)$ на функцию $\mathfrak{C}(n)$. 3.4. Метод расширенияСжимающие стратегии, реализованные в алгоритмах 1 и 2, дают лучшие из известных на данный момент верхних оценок для функции Черни в случае произвольных ДКА. Однако наиболее впечатляющие частичные результаты, доказывающие гипотезу Черни для некоторых специальных классов автоматов, были получены с помощью другого алгоритма, строящего синхронизирующее слово снизу вверх. Чтобы описать этот алгоритм, введём одно обозначение. Для ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$, подмножества $P\subseteq Q$ и слова $w\in\Sigma^*$ обозначим через $Pw^{-1}$ полный прообраз $P$ относительно действия $w$: Отметим, что $P(uv)^{-1}=(Pv^{-1})u^{-1}$. Для $q\in Q$ договоримся писать $qw^{-1}$ вместо $\{q\}w^{-1}$. Тот факт, что слово $w\in\Sigma^*$ синхронизирует автомат $\mathscr{A}$ к состоянию $s$, в этих обозначениях запишется равенством $sw^{-1}=Q$. Назовём собственное подмножество $P\subset Q$ расширяемым, если существует слово $v\in\Sigma^*$, для которого $|Pv^{-1}|>|P|$; такое слово называется расширяющим для подмножества $P$. Алгоритм 3 собирает синхронизирующее слово из расширяющих слов в противоположность алгоритму 1, который работает со сжимающими словами. В то время как нахождение сжимающих слов сводится к поиску в автомате 2-подмножеств и потому реализуемо за полиномиальное от размера автомата время, задача о существовании слова, расширяющего данное собственное подмножество, $\mathbf{PSPACE}$-полна даже для синхронизируемых ДКА (см. [27; предложение 5]). Мы обсуждали в п. 3.3, что в круге вопросов, связанных с гипотезой Черни, можно ограничиться рассмотрением сильно связных автоматов. В сильно связном синхронизируемом ДКА расширяемо любое собственное подмножество, но задача нахождения кратчайшего слова, расширяющего данное подмножество, остаётся вычислительно трудной и для таких автоматов (см. [27; следствие 14]). Поэтому неясно, допускает ли алгоритм 3 полиномиальную от размера автомата имплементацию. Некоторые типы ДКА, для которых такая полиномиальная имплементация возможна, рассмотрены в [28]. Анализ поведения алгоритма 3 в среднем случае представляется важной и интересной исследовательской проблемой, по которой пока нет никаких теоретических результатов, но имеются некоторые экспериментальные данные (см. [148]). В общем случае не известна никакая нетривиальная верхняя оценка длины слов, которые основной цикл алгоритма 3 добавляет к текущему слову. Однако можно выделить некоторые случаи, в которых имеются достаточно сильные оценки этой длины. Назовём $n$-автомат $\alpha$-расширяемым, где $\alpha$ – положительная константа, если в нём каждое собственное неодноэлементное множество состояний расширяемо словом длины не более $\alpha n$. Следующее фольклорное наблюдение объясняет значение этого свойства. Предложение 3.4. Каждый $\alpha$-расширяемый ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ c $n>2$ состояниями синхронизируем, и его порог синхронизации не превышает $1+\alpha n(n-2)$. В частности, гипотеза Черни верна для $1$-расширяемых автоматов. Доказательство. При $n>2$ у множества $Q$ есть собственные неодноэлементные подмножества. Если $S\subset Q$ – такое подмножество и $v\in\Sigma^*$ – слово, расширяющее $S$, то найдётся состояние $s\in S$, для которого $|sv^{-1}|>1$. Если $v=a_1\cdots a_\ell$, где $a_1,\dots,a_\ell\in\Sigma$, то пусть $i\in\{1,\dots,n\}$ – наибольший номер, для которого $|s(a_ia_{i+1}\cdots a_\ell)^{-1}|>1$. Тогда можно взять букву $a_i$ и (единственное) состояние из множества $s(a_{i+1}\cdots a_\ell)^{-1}$ в качестве пары $(q,a)$, необходимой для инициализации в строке 4 алгоритма 3.
Алгоритм 3 проходит основной цикл не более $n-2$ раз, поскольку цикл начинается при $|P|\geqslant2$, а каждое прохождение цикла увеличивает $|P|$ по крайней мере на 1. При этом всякий раз добавляется слово длины не более $\alpha n$. Следовательно, длина синхронизирующего слова, возвращаемого алгоритмом, не превышает $1+\alpha n(n-2)$. При $\alpha=1$ получается оценка $1+n(n-2)=(n-1)^2$ из гипотезы Черни. Предложение доказано. Подход к гипотезе Черни через 1-расширяемость возник в статье Пэна [133]. Пэн показал, что каждый ДКА с простым числом состояний, в котором одна из букв циклически переставляет состояния, а какая-то другая буква сжимает множество состояний, 1-расширяем. Луи Дюбюк [62] развил этот результат Пэна, доказав 1-расширяемость синхронизируемого автомата, в котором некоторая буква действует как циклическая перестановка множества всех состояний. (Автоматы с этим свойством называются циклическими.) Яркко Кари [100] установил 1-расширяемость эйлеровых синхронизируемых автоматов. (Напомним, что, применяя термины теории графов к автомату, мы подразумеваем, что они применяются к носителю автомата. Граф называется эйлеровым, если в нём есть цикл, содержащий каждое ребро ровно один раз.) Итак, 1-расширяемость позволяет подтвердить гипотезу Черни в нескольких интересных частных случаях. Однако в общем случае доказать эту гипотезу через 1-расширяемость невозможно, поскольку существуют сильно связные синхронизируемые автоматы, не являющиеся 1-расширяемыми. Первым таким примером был 6-автомат $\mathscr{K}_6$, открытый Кари [99]; он изображён на рис. 20, из которого понятно действие букв. Этот автомат синхронизируем, его кратчайшее синхронизирующее слово имеет длину 25. Кари нашёл $\mathscr{K}_6$ как контрпример к обобщению гипотезы Черни, предложенному в диссертации Пэна [132], но этот автомат обладает и другими примечательными свойствами. В частности, можно проверить, что в $\mathscr{K}_6$ никакое множество из более чем четырёх состояний не будет полным прообразом множества $\{2,3,4,5\}$ относительно действия слова длины 6 (как требуется в определении $1$-расширяемости) или даже 7. 2-расширяемость (и следовательно, в силу предложения 3.4, квадратичная верхняя оценка на порог синхронизации) была доказана для ряда классов синхронизируемых ДКА (см. [80], [154], [158], [155]). Мари-Пьер Беал, М. В. Берлинков и Доминик Перрэн [18], [19] установили, что это свойство в слегка ослабленной, но достаточной для квадратичной верхней оценки на порог синхронизации форме выполнено для синхронизируемых однокластерных автоматов. ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется однокластерным, если есть такие $q\in Q$ и $a\in\Sigma$, что из любого состояния найдётся путь в $q$, рёбра которого помечены только буквой $a$. (Например, автоматы $\mathscr{C}_n$ и $ \mathscr{W}_n$, изображённые на рис. 15, однокластерные, а автомат Кари $\mathscr{K}_6$ нет. Однокластерными являются и такие важные для приложений ДКА, как декодеры конечных максимальных префиксных кодов, см. п. 1.4.) Для буквы $a$ из определения однокластерности в $\mathscr{A}$ есть ровно один простой цикл, рёбра которого помечены буквой $a$; назовём его $a$-циклом. Если обозначить через $C$ множество вершин $a$-цикла, то несложно понять, что $Q \operatorname{.} a^{|Q|-|C|}=C$. Приводимый далее алгоритм 4 – это модификация алгоритма 3, использующая указанное соображение.  В [18], [19] показано, что длина слова, добавляемого при каждом прохождении основного цикла алгоритма 4, не превышает $2n$, где $n:=|Q|$, что влечёт верхнюю оценку вида $2n^2+o(n^2)$ на $\operatorname{rt}(\mathscr{A})$. Аналогичный результат получили Артуро Карпи и Флавио Д’Алессандро [40], [41]. Стейнберг [173], [174] обобщил описанный выше подход и немного улучшил явное выражение для члена $o(n^2)$ в оценках из [18], [19], [40], [41]. А именно, Стейнберг проверил, что $\operatorname{rt}(\mathscr{A})\leqslant2n^2-9n+14$, где, как и выше, $\mathscr{A}$ – однокластерный синхронизируемый $n$-автомат. В [174] Стейнберг также доказал гипотезу Черни для однокластерных ДКА, у которых размер $a$-цикла – простое число. В [42] Карпи и Д’Алессандро дали верхнюю оценку с лучшей на сегодняшний день асимптотикой, установив, что порог синхронизации однокластерного синхронизируемого $n$-автомата не превышает $2n^{2}-4n+1-2(n-1)\ln(n/2)$. Старший коэффициент 2 в первоначальных оценках из [18], [19], [40], [41] устоял и при последующих улучшениях, полученных в рамках метода расширения. Эту закономерность объясняет результат Берлинкова [22]: он указал серию синхронизируемых однокластерных ДКА $\mathscr{B}_n=\langle\{0,1,\dots,n-1\},\{a,b\}\rangle$, в которой для каждого $\alpha<2$ есть автоматы, не являющиеся $\alpha$-расширяемыми. Автомат $\mathscr{B}_n$ изображён на рис. 21. Действие букв в $\mathscr{B}_n$ определено так:
$$
\begin{equation*}
\begin{aligned} \, i \operatorname{.} a&:=\begin{cases} i+1, &\text{если } i<n-2,\\ 0, &\text{если } i=n-2,\\ 2, &\text{если } i=n-1; \end{cases} \\ i \operatorname{.} b&:=\begin{cases} n-1, &\text{если}\ i=0, \\ i, &\text{если}\ 0<i<n-1, \\ 0, &\text{если}\ i=n-1. \end{cases} \end{aligned}
\end{equation*}
\notag
$$
Можно проверить, что в $\mathscr{B}_n$ кратчайшим расширяющим словом для подмножества $\{0,{n-1}\}$ является слово $a^{n-2}ba^{n-2}$ длины $2n-3$. Поэтому ни при каком $n> 3/(2-\alpha)$ автомат $\mathscr{B}_n$ не будет $\alpha$-расширяемым. 2-расширяемость установлена и для некоторых других типов синхронизируемых автоматов (см. [42], [154], [158], [155]). Однако надежды на то, что квадратичную по $n$ оценку на порог синхронизации произвольных синхронизируемых $n$-автоматов можно получить, доказав их $\alpha$-расширяемость для какого-то $\alpha$ и применив предложение 3.4, не оправдались. Киселевич и Шикула [105] построили серию синхронизируемых ДКА $\mathscr{K\!\!S}_{2m-1}=\langle\{1,2,\dots,2m-1\},\{a,b\}\rangle$, в которой для каждого $\alpha$ найдётся автомат, не являющийся $\alpha$-расширяемым. Автомат $\mathscr{K\!\!S}_{2m-1}$ изображён на рис. 22. Действие букв в нём определено так:
$$
\begin{equation*}
\begin{aligned} \, i \operatorname{.} a&:=\begin{cases} 1, &\text{если}\ i=m,\\ m+1, &\text{если}\ i=2m-1,\\ i+1 &\text{в остальных случаях}; \end{cases} \\ i \operatorname{.} b&:=\begin{cases} i, &\text{если}\ 1\leqslant i\leqslant m-1,\\ 2m-1, &\text{если}\ i=m,\\ i-m &\text{в остальных случаях}. \end{cases} \end{aligned}
\end{equation*}
\notag
$$
Можно проверить, что в $\mathscr{K\!\!S}_{2m-1}$ длина кратчайшего слова, расширяющего подмножество $\{m+1,\dots,2m-1\}$ (т. е. “верхнюю строку” на рис. 22), равна $2+m\lceil(m-2)/2\rceil$. Последнее выражение растёт быстрее любой линейной функции от числа $2m-1$, поэтому для любого $\alpha$ можно подобрать $m$, начиная с которого автоматы $\mathscr{K\!\!S}_{2m-1}$ не будут $\alpha$-расширяемыми. В [28] предпринят алгебраический анализ метода расширения, приведший к некоторым обобщениям метода и усилениям полученных с его помощью результатов. Эти обобщения будут представлены в разделе второй статьи цикла, посвящённом связям между теорией синхронизируемых ДКА и теорией неотрицательных матриц и цепей Маркова. Упомянем ещё статью [87], результаты которой в некотором смысле уменьшают “зазор” между сжимающим алгоритмом 1 и расширяющим алгоритмом 3. А именно, в [87] продемонстрировано, что для большинства типов автоматов, рассмотренных в данном пункте, т. е. для ДКА, для которых хорошо работает метод расширения, сжимающий алгоритм работает лучше, чем в общем случае. Так, например, для синхронизируемых циклических ДКА алгоритм 1 возвращает синхронизирующее слово длины не больше $n^2\ln n$ (см. [87; теорема 13]). 3.5. Сводка частичных результатовЭтот пункт носит справочный характер. В нём собраны основные результаты, устанавливающие справедливость ограничения гипотезы Черни на различные классы ДКА. В дополнение к этому перечислены классы автоматов, для которых гипотеза Черни не доказана, но известна квадратичная по числу состояний верхняя оценка для порога синхронизации. Некоторые из обсуждаемых в этом пункте результатов уже упоминалось выше; мы сочли уместным привести их и здесь для полноты сводного списка. Сведения, относящиеся к каждому классу автоматов, организованы в следующем формате:
A. Типы ДКА с порогом синхронизации $(n-1)^2$ или близким к $(n-1)^2$. А$1^\unicode{8224}$. Циклические автоматы. $\bullet$ Определение: ДКА называется циклическим, если одна из его букв действует как циклическая перестановка множества всех состояний. $\bullet$ Верхняя оценка: $(n-1)^2$ (см. [62]). $\bullet$ Метод: 1-расширяемость (см. п. 3.4). $\bullet$ Нижняя оценка: $(n-1)^2$, поскольку автоматы $\mathscr{C}_n$ из серии Черни циклические. А2. Однокластерные автоматы с циклом простой длины. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется однокластерным, если есть такие $q\in Q$ и $a\in\Sigma$, что из любого состояния найдётся путь в $q$, рёбра которого помечены только буквой $a$. Для всякой такой буквы $a$ в $\mathscr{A}$ есть ровно один простой цикл, рёбра которого помечены $a$; к рассматриваемому здесь типу относятся однокластерные ДКА, в которых для какой-то буквы этот цикл содержит простое число состояний. $\bullet$ Верхняя оценка: $(n-1)^2$ (см. [174]). $\bullet$ Метод: 2-расширяемость (см. п. 3.4) с некоторыми дополнительными техническими ухищрениями. $\bullet$ Нижняя оценка: если $n$ – простое число, то $(n-1)^2$, поскольку тогда автомат $\mathscr{C}_n$ из серии Черни относится к рассматриваемому типу; для составных $n$ точная нижняя оценка неизвестна. А$3^\unicode{8224}$. Ориентируемые автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется ориентируемым17, если состояния из $Q$ можно расположить в циклическом порядке18 $q_0,q_1,\dots,q_{n-1}$, где $n=|Q|$, так, чтобы действие букв из $\Sigma$ сохраняло этот циклический порядок. Чтобы строго определить последнее условие, будем говорить, что последовательность $p_0,p_1,\dots,p_{m-1}$ (не обязательно различных) состояний из $Q$ правильно ориентирована, если, оставив в ней ровно одно состояние из каждого блока $p_i=p_{i+1\!\!\pmod m}=\cdots=p_{i+k\!\!\pmod m}$ одинаковых соседних состояний, получим подпоследовательность некоторой циклической перестановки последовательности $q_0,q_1,\dots,q_{n-1}$. Буква $a\in\Sigma$ сохраняет циклический порядок, если последовательность образов $q_0 \operatorname{.} a,q_1 \operatorname{.} a,\dots,q_{n-1} \operatorname{.} a$ правильно ориентирована. $\bullet$ Верхняя оценка: $(n-1)^2$ (см. [64]). $\bullet$ Метод основан на следующем свойстве ориентируемых автоматов: для любого слова $w\in\Sigma^*$ и любого интервала $I\subseteq Q$ полный прообраз $Iw^{-1}$ является интервалом19 (см. [64; лемма 1]). Если $w:=a_1\cdots a_\ell$, где $a_1,\dots,a_\ell\in\Sigma$, – синхронизирующее слово, возвращаемое алгоритмом 3, а $q\in Q$ – состояние, с которого алгоритм 3 начинает работу, то все подмножества $q(a_ia_{i+1}\cdots a_\ell)^{-1}$ различны и являются неодноэлементными интервалами. (Иллюстрацией может служить рис. 11, где видно, что подъём от состояния $q:=1$ до множества $Q:=\{0,1,2,3\}$ происходит исключительно через интервалы.) Нетрудно подсчитать, что в $n$-элементном циклически упорядоченном множестве имеется $(n-1)^2$ неодноэлементных интервалов, и, значит, $\ell\leqslant(n-1)^2$. $\bullet$ Нижняя оценка: $(n-1)^2$, поскольку автоматы $\mathscr{C}_n$ из серии Черни ориентируемые. $\bullet$ Комментарии: В [10; теорема 2.2] верхняя оценка из [64] распространена на более широкий класс синхронизируемых полуориентируемых автоматов. ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ полуориентируем, если состояния из $Q$ можно расположить в циклическом порядке $q_0,q_1,\dots,q_{n-1}$, где $n=|Q|$, и для каждой буквы $a\in\Sigma$ одна из последовательностей $q_0 \operatorname{.} a,q_1 \operatorname{.} a,\dots,q_{n-1} \operatorname{.} a$ и $q_{n-1} \operatorname{.} a,q_{n-2} \operatorname{.} a,\dots,q_0 \operatorname{.} a$ правильно ориентирована. Ещё одно, более громоздко формулируемое обобщение обсуждается в пункте А4. А$4^\unicode{8224}$. Автоматы, сохраняющие интервалы графов. $\bullet$ Определение: Пусть $\Delta$ – граф, множество вершин которого есть множество $Q$ состояний ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$. (Предостережение: граф $\Delta$, вообще говоря, отличен от носителя ДКА $\mathscr{A}$, хотя и имеет с последним одинаковое множество вершин.) Для $p,r\in Q$ назовём путь из $p$ в $r$ в графе $\Delta$ сингулярным, если ни $p$, ни $r$ не встречаются на этом пути как промежуточные вершины. Определим $[p,r]$ как пустое множество, если в $\Delta$ нет пути из $p$ в $r$, и как множество
$$
\begin{equation*}
\{q\in Q\mid q\ \text{встречается на сингулярном пути из $p$ в $r$}\},
\end{equation*}
\notag
$$
если в $\Delta$ есть путь из $p$ в $r$. Граф $\Delta$ назовём плотным, если для всех $p,q,r\in Q$ из того, что $[p,r],[r,p],[p,q],[q,r]\ne\varnothing$, следует, что либо $q\in[p,r]$, либо $q\in[r,p]$. Будем говорить, что $\mathscr{A}$ сохраняет интервалы графа $\Delta$, если для любых $p,r\in Q$ и любой буквы $a\in\Sigma$ выполнены следующие условия:
$\bullet$ Верхняя оценка: $(n-1)^2$ (см. [84; следствие 2.1]). $\bullet$ Метод: индукция по числу состояний и разбор случаев. $\bullet$ Нижняя оценка: $(n-1)^2$, поскольку автоматы $\mathscr{C}_n$ из серии Черни попадают в данный класс (с циклом $0\to1\to2\to\dots\to n-1\to 0$ в роли графа $\Delta$). А$5^\unicode{8224}$. Автоматы с 2-пересечениями. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется автоматом с 2-пересечениями, если для любой буквы $a\in\Sigma$ выполнено одно из следующих условий:
$\bullet$ Верхняя оценка: $(n-1)^2$ (см. [85; теорема 2.1]). $\bullet$ Метод: сведе́ние к ДКА типов A1 и A6 и разбор остающихся случаев. $\bullet$ Нижняя оценка: $(n-1)^2$, поскольку автоматы $\mathscr{C}_n$ из серии Черни попадают в данный класс. А6. Эйлеровы автоматы. ДКА называется эйлеровым, если в его носителе есть цикл, содержащий каждое ребро ровно один раз. $\bullet$ Верхняя оценка: $n^2-3n+3$ (см. [100; теорема 3]). $\bullet$ Метод: 1-расширяемость (см. п. 3.4) с дополнительным улучшением: для эйлеровых автоматов длина слова, добавляемого при каждом прохождении основного цикла алгоритма 3, не превышает $n-1$. Поэтому алгоритм возвращает синхронизирующее слово длины не больше $1+(n-2)(n-1)=n^2-3n+3$. $\bullet$ Нижняя оценка: $\lfloor(n^2-3)/2\rfloor$ (см. [178]). $\bullet$ Комментарии: Верхняя оценка $n^2-3n+3$ распространена на класс псевдоэйлеровых автоматов в [173; теорема 3]. ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется псевдоэйлеровым, если можно так приписать буквам из $\Sigma$ положительные веса, чтобы для каждого состояния $q\in Q$ как сумма весов меток рёбер с началом $q$, так и сумма весов меток рёбер с концом $q$ равнялась 1. (Для эйлеровых автоматов последнее условие выполнено, если каждой букве приписать вес $1/|\Sigma|$.) Нижняя оценка $\lfloor(n^2-3)/2\rfloor$ из [178] реализуется на серии эйлеровых автоматов с четырьмя входными буквами. Автоматы из этой же серии показывают, что верхняя оценка $n-1$ на длину слова, добавляемого при прохождении основного цикла алгоритма 3 на эйлеровых автоматах, вообще говоря, неулучшаема. В классе эйлеровых ДКА с двумя входными буквами П. В. Мартюгин (не опубликовано) указал серию синхронизируемых $n$-автоматов ($n$ нечётно) с предположительным порогом синхронизации $(n^2-5)/2$. Это предположение подтверждено полным перебором эйлеровых $n$-автоматов с двумя входными буквами при $n=5,7,9,11$, причём при каждом из этих $n$ автомат из серии Мартюгина оказался единственным с порогом синхронизации $(n^2-5)/2$. В общем случае предположение, однако, не доказано, и наибольшей доказанной нижней границей для максимума порогов синхронизации синхронизируемых эйлеровых $n$-автоматов с двумя входными буквами ($n$ нечётно) пока остаётся оценка $(n^2-3n+4)/2$ из [86]. А7. Автоматы с буквой малого ранга. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется автоматом с буквой малого ранга, если есть такая буква $a\in\Sigma$, что $|Q \operatorname{.} a|\leqslant\sqrt[3]{6|Q|-6}$ . $\bullet$ Верхняя оценка: $(n-1)^2$ (см. [28; следствие 13]). $\bullet$ Метод: следствие теоремы 6 из [28], полученной с помощью усовершенствованного метода расширения. $\bullet$ Нижняя оценка: неизвестна. $\bullet$ Комментарии: Пионерский результат по проблеме Черни для автоматов с буквой малого ранга получен в [134; теорема 1]. В работе [134] на “степень сжатия” буквы $a$ накладывалось более сильное условие $|Q \operatorname{.} a|\leqslant1+\log_2|Q|$. А8. Автоматы без инволюций. $\bullet$ Определение: ДКА $\mathscr{A}$ называется автоматом без инволюций, если в $\mathscr{A}$ нет состояния $q$ и слова $w$ таких, что $q \operatorname{.} w\ne q=q \operatorname{.} w^2$. В алгебраических терминах это означает, что моноид переходов автомата $\mathscr{A}$ не содержит подгрупп чётного порядка. $\bullet$ Верхняя оценка: $(n-1)^2$ (см. [181; теорема 6]). $\bullet$ Метод: модификация подхода из [180] (см. п. B2). $\bullet$ Нижняя оценка: Известна только линейная нижняя оценка $n+\lfloor n/2\rfloor-2$, которая следует из [7]. В случае сильно связных синхронизируемых автоматов без инволюций пока не известны примеры с порогом синхронизации больше $n-1$. $\bullet$ Комментарии: в доказательстве из [181] есть не вполне ясные места. B. Типы ДКА с порогом синхронизации от $n$ до $n(n-1)/2$. B$1^\unicode{8224}$. Автоматы с нулём. $\bullet$ Определение: ДКА называется автоматом с нулём, если в нём есть состояние, фиксируемое всеми буквами. $\bullet$ Верхняя оценка: $n(n-1)/2$ ([149; теорема 1], см. также [157; теорема 6.1]). $\bullet$ Метод: см. доказательство предложения 3.3. $\bullet$ Нижняя оценка: $n(n-1)/2$ для ДКА с неограниченным алфавитом (см. доказательство предложения 3.3). Для автоматов с двумя входными буквами наилучшая на сегодня нижняя граница для максимума порогов синхронизации синхронизируемых $n$-автоматов с нулём составляет $n^2/4+2n-9$; она достигается при $n\equiv4\!\pmod{12}$, начиная с $n=16$, на серии ДКА из [14]. B2. Апериодические автоматы. $\bullet$ Определение: ДКА $\mathscr{A}$ называется апериодическим, если в $\mathscr{A}$ нет состояния $q$ и слова $w$ таких, что $q \operatorname{.} w\ne q=q \operatorname{.} w^k$ для некоторого $k$. В алгебраических терминах это означает, что моноид переходов автомата $\mathscr{A}$ не содержит неодноэлементных подгрупп. $\bullet$ Верхняя оценка: $n(n-1)/2$ (см. [180; теорема 10]). $\bullet$ Метод: Класс апериодических автоматов замкнут относительно взятия подавтоматов и факторавтоматов, а функция $n(n-1)/2$ удовлетворяет неравенству (11). По лемме 3.3 верхнюю оценку $n(n-1)/2$ достаточно проверить для сильно связных синхронизируемых апериодических ДКА и для синхронизируемых апериодических ДКА с нулём. Во втором случае она верна для всех ДКА с нулём (см. п. В1). Сильно связный апериодический ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ всегда синхронизируем [180; теорема 9] и допускает нетривиальное отношение частичного порядка $\leqslant$, устойчивое относительно действия букв: если $p\leqslant r$ для каких-то $p,r\in Q$, то $p \operatorname{.} a\leqslant r \operatorname{.} a$ для любой буквы $a\in\Sigma$. Поэтому если $p \operatorname{.} w=r \operatorname{.} w$ для некоторого слова $w\in\Sigma^*$, то это слово переводит в состояние $p \operatorname{.} w=r \operatorname{.} w$ любое состояние $q\in Q$ такое, что $p\leqslant q\leqslant r$. Это позволяет собрать синхронизирующее слово длины $\leqslant n(n-1)/2$ из слов длины $\leqslant n-1$, переводящих максимальные относительно порядка $\leqslant$ состояния в минимальные или наоборот. (В силу сильной связности автомата $\mathscr{A}$ для любых двух его состояний есть слово длины $\leqslant n-1$, переводящее одно из состояний в другое.) Ясно, что либо число максимальных, либо число минимальных состояний не превосходит $n/2$. Для аккуратной реализации описанного подхода нужно ещё применить индукцию по числу состояний. $\bullet$ Нижняя оценка: Известна только линейная нижняя оценка $n+\lfloor n/2\rfloor-2$, которая следует из [7]. В случае сильно связных апериодических автоматов не известны примеры с порогом синхронизации больше $n-1$, и предполагается, что порог синхронизации сильно связных апериодических $n$-автоматов не превосходит $n-1$. Это предположение подтверждено полным перебором сильно связных апериодических $n$-автоматов с двумя входными буквами при $n\leqslant11$ и с тремя входными буквами при $n\leqslant7$ (см. [176; § 7.4.4]). См. также комментарий к п. D3. $\bullet$ Комментарии: в [188] верхняя оценка на порог синхронизации сильно связных апериодических $n$-автоматов улучшена до $\lfloor n(n+1)/6\rfloor$. B$3^\unicode{8224}$. Автоматы с моноидом переходов из $\mathbf{EDS}$. $\bullet$ Определение: Класс $\mathbf{DS}$ состоит из всех конечных моноидов $M$ таких, что для всех $x,y,z\in M$ выполнена импликация20:
$$
\begin{equation*}
\text{если}\quad MxM=MyM=MzM=Mx^2M,\quad \text{то}\quad MxM=MyzM.
\end{equation*}
\notag
$$
Элемент $e$ моноида $M$ называется идемпотентом, если $e^2=e$. Класс $\mathbf{EDS}$ состоит из всех конечных моноидов $M$ со следующим свойством: подмоноид, порождённый всеми идемпотентами из $M$, лежит в $\mathbf{EDS}$. Здесь рассматриваются ДКА, моноиды переходов которых принадлежат $\mathbf{EDS}$. $\bullet$ Верхняя оценка: $n(n-1)/2$ (см. [5; следствие 4.3]). $\bullet$ Метод: используется информация о линейных представлениях моноидов из $\mathbf{EDS}$, вытекающая из классической теории полугрупповых представлений (теория Манна–Понизовского). $\bullet$ Нижняя оценка: $n(n-1)/2$ для ДКА с неограниченным алфавитом, поскольку автоматы $\mathscr{R}_n$ из серии Рысцова (см. доказательство предложения 3.3) попадают в данный класс. Для синхронизируемых ДКА над фиксированным алфавитом из этого класса, а также для сильно связных синхронизируемых ДКА из него о нижних границах значений для максимума порогов синхронизации практически ничего не известно. B4. Декодеры конечных максимальных префиксных кодов. $\bullet$ Определение: Множество $X\subset\Sigma^+$ называется префиксным кодом над $\Sigma$, если слова из $X$ не являются префиксами друг друга. Префиксный код называется максимальным, если он не содержится ни в каком другом префиксном коде над $\Sigma$. Декодер конечного максимального префиксного кода $X\subset\Sigma^+$ – это ДКА $\mathscr{A}_X=\langle Q,\Sigma\rangle$, где $Q$ – множество всех префиксов слов из $X$, а функция перехода определена так:
$$
\begin{equation*}
q \operatorname{.} a:=\begin{cases} qa, & \text{если $qa$ - префикс слова из $X$}, \\ \varepsilon, & \text{если $qa \in X$}. \end{cases}
\end{equation*}
\notag
$$
$\bullet$ Верхняя оценка: $2+(n+h-1)(h^3-h)/6$, где $h=\lceil\log_{|\Sigma|}n\rceil$ (см. [28; следствие 17]). $\bullet$ Метод: усовершенствованный метод сжатия. $\bullet$ Нижняя оценка: $2n-5$ при чётном $n$ и $2n-7$ при нечётном $n$, если $|\Sigma|=2$ (см. [33]). Для $|\Sigma|\geqslant3$ в [28; теорема 19] получена нижняя оценка $2\lceil n/(|\Sigma|+1)\rceil$. B5. Полумонотонные автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется полумонотонным, если на $Q$ есть линейный порядок $\leqslant$ и для любой буквы $a\in\Sigma$ либо при всех $p,r\in Q$ из $p\leqslant r$ следует $p \operatorname{.} a\leqslant r \operatorname{.} a$, либо при всех $p,r\in Q$ из $p\leqslant r$ следует $p \operatorname{.} a\geqslant r \operatorname{.} a$. (Другими словами, функция $q\mapsto q \operatorname{.} a$ либо монотонно неубывающая, либо монотонно невозрастающая.) $\bullet$ Верхняя оценка: $n(n-1)/2$ в общем случае; $2n-3$, если у $\mathscr{A}$ имеется такая буква $c$, что функция $q\mapsto q \operatorname{.} c$ есть монотонно убывающая биекция (см. [10; предложение 3.2]). $\bullet$ Метод: Общий случай основан на следующих трёх соображениях. 1) В полумонотонном автомате для любого слова $w\in\Sigma^*$ и любого интервала $I$ линейно упорядоченного множества $\langle Q,\leqslant\,\rangle$ полный прообраз $Iw^{-1}$ является интервалом21. 2) Если $w:=a_1\cdots a_\ell$, где $a_1,\dots,a_\ell\in\Sigma$, – синхронизирующее слово, возвращаемое алгоритмом 3, а $q\in Q$ – состояние, с которого алгоритм 3 начинает работу, то все подмножества $q(a_ia_{i+1}\cdots a_\ell)^{-1}$ различны и являются неодноэлементными интервалами. 3) В $n$-элементном линейно упорядоченном множестве имеется $n(n-1)/2$ неодноэлементных интервалов. Отсюда следует, что $\ell\leqslant n(n-1)/2$. При наличии буквы, действующей как монотонно убывающая биекция, используется сведе́ние к монотонным ДКА (см. п. C1). $\bullet$ Нижняя оценка: $2n-3$ при $n\equiv3\!\pmod{4}$ (см. [10; предложение 3.1]). B$6^\unicode{8224}$. 0-монотонные автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ с нулём 0 называется 0-монотонным, если на $Q\setminus\{0\}$ есть линейный порядок $\leqslant$ и для любой буквы $a\in\Sigma$ и любых $p,r\in Q\setminus\{0\}$ из соотношений $p\leqslant r$ и $p \operatorname{.} a,r \operatorname{.} a\ne 0$ следует, что $p \operatorname{.} a\leqslant r \operatorname{.} a$. $\bullet$ Верхняя оценка: $n+\lfloor n/2\rfloor-2$ (см. [7; теорема 1]). $\bullet$ Метод: сведе́ние к некоторым свойствам монотонных ДКА (см. п. C1). $\bullet$ Нижняя оценка: $n+\lfloor n/2\rfloor-2$ (см. [7; теорема 2]). B7. Конечно порождённые автоматы. $\bullet$ Определение: ДКА $\mathscr{A}$ с входным алфавитом $\Sigma$ называется конечно порождённым, если существует конечное подмножество $W\subset\Sigma^*$ такое, что $\operatorname{Sync}\mathscr{A}=\Sigma^*W\Sigma^*$. В алгебраических терминах это значит, что язык синхронизирующих слов автомата $\mathscr{A}$ является конечно порождённым идеалом моноида $\Sigma^*$. $\bullet$ Верхняя оценка: $3n-5$ (см. [139; теорема 4]). $\bullet$ Метод: используется характеризация конечно порождённых автоматов из [139; теорема 1] и оценка из [134; предложение 5]. $\bullet$ Нижняя оценка: $n-1$ (см. [139; обсуждение примера 1]). C. Типы ДКА с порогом синхронизации $n-1$. C$1^\unicode{8224}$. Монотонные автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется монотонным, если на $Q$ есть линейный порядок $\leqslant$ и для любой буквы $a\in\Sigma$ и всех $p,r\in Q$ из того, что $p\leqslant r$, следует, что $p \operatorname{.} a\leqslant r \operatorname{.} a$. $\bullet$ Верхняя оценка: $n-1$ (см. [11]). $\bullet$ Метод: индукция по числу состояний. $\bullet$ Нижняя оценка: $n-1$, примером может служить серия монотонных автоматов $\mathscr{M}_n:=\langle\{0,1,2,\dots,n-1\},\{a\}\rangle$, в которых действие буквы определено правилом:
$$
\begin{equation*}
i. a:=\begin{cases} i-1, &\text{если}\ i>0, \\ 0, &\text{если}\ i=0. \end{cases}
\end{equation*}
\notag
$$
$\bullet$ Комментарии: Насколько можно судить по английской аннотации опубликованной на китайском языке статьи Жен-Хе Куи, Йонг Хе и Ши-Юань Сана [56], в ней верхняя оценка $n-1$ распространена на такие ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$, что на $Q$ есть частичный порядок $\leqslant$, относительно которого в $Q$ есть наибольший и наименьший элементы, и для любой буквы $a\in\Sigma$ и всех $p,r\in Q$ из того, что $p\leqslant r$, следует, что $p \operatorname{.} a\leqslant r \operatorname{.} a$. C$2^\unicode{8224}$. Обобщённо монотонные автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется $\rho$-монотонным, где $\rho$ – конгруэнция на $\mathscr{A}$, если на $Q$ есть частичный порядок $\leqslant$ такой, что два состояния сравнимы относительно $\leqslant$ тогда и только тогда, когда они лежат в одном $\rho$-классе, и для любой буквы $a\in\Sigma$ и всех $p,r\in Q$ из того, что $p\leqslant r$, следует, что $p \operatorname{.} a\leqslant r \operatorname{.} a$. ДКА $\mathscr{A}$ называется обобщённо монотонным, если он допускает цепочку конгруэнций такую, что $\rho_0$ – отношение равенства, $\rho_\ell$ – универсальное отношение на $Q$ и для каждого $i=1,\dots,\ell$ факторавтомат $\mathscr{A}/\rho_{i-1}$ является $\rho_i/\rho_{i-1}$-монотонным.$\bullet$ Верхняя оценка: $n-1$ (см. [12; теорема 1.2]). $\bullet$ Метод: индукция по числу состояний. $\bullet$ Нижняя оценка: $n-1$, поскольку автоматы $\mathscr{M}_n$ из п. C1 попадают в данный класс. C$3^\unicode{8224}$. Автоматы с моноидом переходов из $\mathbf{DS}$. $\bullet$ Определение: Класс моноидов $\mathbf{DS}$ определён в п. B3 выше. Здесь рассматриваются ДКА, моноиды переходов которых принадлежат $\mathbf{DS}$. $\bullet$ Верхняя оценка: $n-1$ (см. [5; теорема 2.6]). $\bullet$ Метод: используется информация о линейных представлениях моноидов из $\mathbf{DS}$ из статьи [3]. $\bullet$ Нижняя оценка: $n-1$, поскольку автоматы $\mathscr{M}_n$ из п. C1 попадают в данный класс. $\bullet$ Комментарии: Данный класс автоматов содержит ряд классов, для которых верхняя оценка $n-1$ была ранее установлена И. К. Рысцовым (см. [153], [157], [156]), а также класс так называемых слабо ациклических автоматов, для которого ту же оценку доказал А. Рыжиков [160]. В терминах моноидов переходов в [153], [157], [156] изучались автоматы с коммутативными или близкими к коммутативным моноидами переходов, а в [160] – автоматы, моноиды переходов которых $\mathcal{R}$-тривиальны22. Нетрудно видеть, что и коммутативные, и $\mathcal{R}$-тривиальные конечные моноиды принадлежат $\mathbf{DS}$. C$4^\unicode{8224}$. Автоматы с двумя идемпотентными буквами. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется автоматом с идемпотентными буквами, если $q \operatorname{.} a=q \operatorname{.} a^2$ для любых $q\in Q$ и $a\in\Sigma$. Здесь рассматриваются такие автоматы при $|\Sigma|=2$. $\bullet$ Верхняя оценка: $n-1$ (см. [189; предложение 5]). $\bullet$ Метод: Класс автоматов с двумя идемпотентными буквами замкнут относительно взятия подавтоматов и факторавтоматов, а функция $n-1$ удовлетворяет неравенству (11). По лемме 3.3 верхнюю оценку $n-1$ достаточно проверить для сильно связного случая и случая ДКА с нулём. Показывается, что сильно связный синхронизируемый автомат с двумя идемпотентными буквами имеет не более двух состояний. Для синхронизируемых автоматов с двумя идемпотентными буквами и с нулём используется индукция по числу состояний. $\bullet$ Нижняя оценка: $n-1$, пример – серия ДКА $\mathscr{F}_n:=\langle\{1,2,\dots,n\},\{a,b\}\rangle$, в которых действие букв определено правилом:
$$
\begin{equation*}
\begin{aligned} \, i \operatorname{.} a&:=\begin{cases} i, &\text{если $i$ нечётно или $i=n$}, \\ i+1, &\text{если $i$ чётно и $i<n$}; \end{cases} \\ i \operatorname{.} b&:=\begin{cases} i, &\text{если $i$ чётно или $i=n$}, \\ i+1, &\text{если $i$ нечётно и $i<n$}. \end{cases} \end{aligned}
\end{equation*}
\notag
$$
$\bullet$ Комментарии: при $|\Sigma|>2$ порог синхронизации $n$-автомата с идемпотентными буквами может достигать $\lfloor n^2/2\rfloor-2n+2$ (см. [189; следствие 3] или [61; § 3]). C5. Медиумы. $\bullet$ Определение: Для ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ буквы $a,b\in\Sigma$ квазиобратны друг другу, если $p \operatorname{.} a=r$ тогда и только тогда, когда $r \operatorname{.} b=p$ для любых различных состояний $p,r\in Q$. Слово из $\Sigma^*$ называется согласованным, если среди его букв нет квазиобратных друг другу. Слово $w\in\Sigma^*$ называется пассивным, если каждая буква встречается в $w$ столько же раз, сколько и буква, квазиобратная к ней. Слово $a_1\cdots a_\ell$, где $a_1,\dots,a_\ell\in\Sigma$, называется пошагово эффективным для состояния $q\in Q$, если $q \operatorname{.} a_1\ne q$ и $q \operatorname{.} a_1\cdots a_i\ne q \operatorname{.} a_1\cdots a_{i-1}$ для всех $i=2,\dots,\ell$. Медиумом называется ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$, удовлетворяющий следующим аксиомам:
$\bullet$ Верхняя оценка: $n-1$ (см. [65; теорема 1]). $\bullet$ Метод: задача сводится к поиску кратчайшего пути во вспомогательном графе без циклов с множеством вершин $Q$. $\bullet$ Нижняя оценка: в [65] утверждается, что верхняя оценка $n-1$ точна, однако пример медиума с порогом синхронизации $n-1$ приведён только для $n=6$. D. Типы ДКА с квадратичной оценкой на порог синхронизации. D1. Однокластерные автоматы. $\bullet$ Определение: см. п. A2. $\bullet$ Верхняя оценка: $2n^{2}-4n+1-2(n-1)\ln(n/2)$ (см. [42; следствие 1]). $\bullet$ Метод: 2-расширяемость (см. п. 3.4), с некоторыми дополнительными техническими ухищрениями. $\bullet$ Нижняя оценка: $(n-1)^2$, поскольку автоматы $\mathscr{C}_n$ из серии Черни однокластерные. $\bullet$ Комментарии: М. В. Берлинков [23] называет квазиоднокластерным степени $d$ ДКА, у которого есть такая буква, что сумма длин всех, кроме одного, простых циклов, помеченных этой буквой, не превышает $d$. (Однокластерные автоматы суть в точности квазиоднокластерные автоматы степени 0; таким образом, параметр $d$ измеряет “отклонение” от однокластерности.) В [23; следствие 11] показано, что порог синхронизации квазиоднокластерного $n$-автомата степени $d$ не превосходит $2^{d}(n-d+1)(2n-d-2)$. D2. Автоматы с полным моноидом переходов. $\bullet$ Определение: ДКА называется автоматом с полным моноидом переходов, если его моноид переходов состоит из всех преобразований множества состояний. $\bullet$ Верхняя оценка: $2n^{2}-6n+5$ (см. [80; теорема 7]). $\bullet$ Метод: 2-расширяемость (см. п. 3.4). $\bullet$ Нижняя оценка: В теореме 4 работы [80] приведена серия $n$-автоматов с $n+1$ входной буквой, с полным моноидом переходов и порогом синхронизации $n(n-1)/2$. В [61; § 5.1] приведена сходная серия $n$-автоматов с $n$ входными буквами и порогом синхронизации $n(n+1)/2$; можно проверить, что и автоматы этой серии имеют полный моноид переходов. Для ДКА с полным моноидом переходов над фиксированным алфавитом нетривиальные нижние оценки неизвестны. D3. Автоматы с простыми идемпотентами. $\bullet$ Определение: ДКА называется автоматом с простыми идемпотентами, если каждая его буква либо действует как перестановка множества состояний, либо фиксирует все состояния, кроме одного. $\bullet$ Верхняя оценка: $2(n-1)^2$ (см. [158; теорема 4]). $\bullet$ Метод: 2-расширяемость (см. п. 3.4). $\bullet$ Нижняя оценка: $(n-1)^2$, ибо автоматы $\mathscr{C}_n$ из серии Черни лежат в этом классе. $\bullet$ Комментарии: в недавней статье И. К. Рысцова [159] показано, что порог синхронизации апериодического $n$-автомата с простыми идемпотентами не превосходит $n-1$. D4. Квазиэйлеровы автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется квазиэйлеровым степени $d$, если выполнены следующие условия:
$\bullet$ Верхняя оценка: $2^d(n-d+1)(n-1)$ (см. [23; теорема 8]). $\bullet$ Метод: усовершенствованный метод расширения. $\bullet$ Нижняя оценка: $(n-1)^2$, так как автоматы $\mathscr{C}_n$ из серии Черни являются квазиэйлеровыми степени 1. (В качестве множества $E_1$ годится множество $\{1,2,\dots,n-1\}$, а в качестве специального состояния $s$ – состояние 1, см. рис. 15. В качестве весов букв $a$ и $b$ годятся любые два положительных числа, дающих в сумме 1.) D5. Регулярные автоматы. $\bullet$ Определение: ДКА $\mathscr{A}=\langle Q,\Sigma\rangle$ называется регулярным, если существует семейство слов $W\subset\Sigma^*$, содержащее пустое слово и удовлетворяющее следующим условиям:
$\bullet$ Верхняя оценка: $2(n-1)^2$ (см. [155; теорема 7] или [154; теорема 7]). $\bullet$ Метод: 2-расширяемость (см. п. 3.4). $\bullet$ Нижняя оценка: $(n-1)^2$, так как автоматы $\mathscr{C}_n$ из серии Черни регулярны. (На роль семейства $W$ при $m=1$ годится множество слов $\{\varepsilon,b,b^2,\dots,b^{n-1}\}$.) $\bullet$ Комментарии: Сходные определения вводили Карпи и Д’Алессандро в работах [40], [42]. В работе [40] они назвали $n$-автомат $\mathscr{A}=\langle Q,\Sigma\rangle$ сильно транзитивным, если для него существует семейство из $n$ слов $\{w_1,\dots,w_n\}\subset\Sigma^*$ такое, что для любых $p,r\in Q$ есть ровно одно слово $w_i$, для которого $p \operatorname{.} w_i=r$. Если $L:=\max\{|w_1|,\dots,|w_n|\}$, то (см. [40; теорема 2])
$$
\begin{equation*}
\operatorname{rt}(\mathscr{A})\leqslant (n-2)(n+L-1)+1.
\end{equation*}
\notag
$$
В [42] $n$-автомат $\mathscr{A}=\langle Q,\Sigma\rangle$ назван локально сильно транзитивным, если для него существуют семейство $\{w_1,\dots,w_k\}\subset\Sigma^*$ из $k$ слов и множество $\{q_1,\dots,q_k\}\subset Q$ из $k$ различных состояний такие, что
$$
\begin{equation*}
\{q \operatorname{.} w_1,\dots,q \operatorname{.} w_k\}=\{q_1,\dots,q_k\}\quad \text{для любого } q\in Q.
\end{equation*}
\notag
$$
Если $L:=\max\{|w_1|,\dots,|w_k|\}$, а $\ell:=\min\{|w_1|,\dots,|w_k|\}$, то (см. [42; предложение 5])
$$
\begin{equation*}
\operatorname{rt}(\mathscr{A})\leqslant (k-1)(n+L+1)-2k\ln\frac{k+1}{2}+\ell.
\end{equation*}
\notag
$$
3.6. Экспериментальные результатыЗначение экспериментальных исследований в изучении автоматов заметно возросло за последние 20–25 лет с распространением всё более мощных и легко доступных компьютеров. Теория автоматов стала во многом следовать методике естественных наук, где первоначальным источником знания служат эксперименты, осмысление результатов которых позволяет строить новые гипотезы и нащупывать пути для их доказательства (или опровержения). Этот процесс затронул и круг вопросов, связанных с гипотезой Черни. Обширные компьютерные эксперименты [13], [58], [60], [103], [104], [176], [179] подтвердили справедливость гипотезы для всех ДКА с 7 или менее состояниями и любым размером входного алфавита, для всех ДКА с тремя входными буквами и 8 состояниями и для всех ДКА с двумя входными буквами и 12 или менее состояниями. Чтобы дать представление о масштабах необходимых вычислений, напомним, что число $n$-автоматов с $m$ входными буквами равно $n^{nm}$, поскольку задание такого автомата равносильно выбору $m$ отображений среди всех $n^{n}$ отображений $n$-элементного множества в себя. Функция $n^{nm}$ очень быстро растёт с ростом $n$ и $m$; например, число ДКА с тремя входными буквами и 8 состояниями равно $8^{24}=2^{72}\approx 4.7223665\cdot 10^{21}$. Для сокращения перебора используется ряд нетривиальных приёмов; обзор используемой здесь техники см. в диссертации Шикулы [176; гл. 6]. Так, в случае 8-автоматов с тремя входными буквами число автоматов, которые реально пришлось проанализировать, удалось сократить до 20 933 723 139. Помимо подтверждения гипотезы Черни для ДКА небольших размеров, переборные эксперименты выявили непредвиденные особенности в распределении возможных порогов синхронизации синхронизируемых автоматов с данным числом состояний. Например, среди синхронизируемых ДКА с 6 состояниями есть автоматы23 с порогом синхронизации 25, но нет ни одного с порогом синхронизации 24. Зазор между максимальным и вторым по величине порогами синхронизации синхронизируемых автоматов с $n\geqslant 6$ впервые обнаружил А. Н. Трахтман [179]. Эксперименты в [179] ограничивались значениями $n\leqslant 10$, но дальнейшие эксперименты подтвердили существование такого зазора также при $n=11$ и $n=12$. В [13; гипотеза 1, (d)] высказано предположение, что при $n>6$ второй по величине возможный порог синхронизации синхронизируемых автоматов с $n$ состояниями равен $n^2-3n+4$ и что при $n>7$ существует единственный (с точностью до изоморфизма и опускания несущественных букв) $n$-автомат, на котором эта величина достигается. А именно, речь идет о серии автоматов $\mathscr{D}_n:=\langle\{0,1,2,\dots,n-1\},\{a,b\}\rangle$, в которых действие букв определено правилами:
$$
\begin{equation*}
i \operatorname{.} a:=\begin{cases} i+1, &\text{если}\ i<n-2, \\ 0, &\text{если}\ i=n-2, \\ 1, &\text{если}\ i=n-1; \end{cases}\qquad i \operatorname{.} b:=i+1\!\!\!\!\pmod{n}.
\end{equation*}
\notag
$$
Типичный автомат из серии $\mathscr{D}_n$ изображён на рис. 23. В переборных экспериментах, описанных в [13], было обнаружено, что при $n>8$ имеется второй зазор в распределении возможных порогов синхронизации синхронизируемых автоматов с $n$ состояниями и двумя входными буквами. А именно, среди таких автоматов не появляются ДКА с порогом синхронизации меньшим, чем $n^2-3n+2$, и бо́льшим, чем $n^2-4n+7$ для нечётных $n$ или $n^2-4n+6$ для чётных $n$. Третий зазор похожего сорта был зарегистрирован при $n>10$ в [104], [176]. Дальнейшее изучение зазоров в распределении порогов синхронизации предпринято в [63]. Феномен “разрывности” порогов синхронизации любопытен сам по себе, но мы остановились на нём главным образом потому, что его обнаружение помогло нащупать интересные связи, до того остававшиеся незамеченными. (Здесь как раз сработала “методика естественных наук”, упомянутая в начале пункта.) А именно, в [13] было подмечено, что наблюдаемое в экспериментах поведение количества синхронизируемых автоматов с фиксированным числом состояний как функции от порога синхронизации весьма сходно с поведением другой величины, обстоятельно исследовавшейся в дискретной математике, – количества примитивных графов с фиксированным числом вершин как функции от значения экспоненты24. Анализ причин такого сходства позволил установить ряд новых обоюдополезных соответствий между синхронизируемыми ДКА и примитивными неотрицательными матрицами; эти взаимосвязи подробно обсуждаются во второй статье цикла. Возвращаясь к обсуждению экспериментальных результатов, связанных с гипотезой Черни, упомянем ещё обширные эксперименты, проводившиеся над случайными автоматами (см. [52], [102], [103], [169]). Во всех этих экспериментах использовалась простейшая модель случайного ДКА с $n$ состояниями и $m$ буквами, в которой такой ДКА есть просто $m$-ка отображений, выбранных равномерно и случайно из всех $n^n$ преобразований множества состояний. В контексте гипотезы Черни эксперименты со случайными ДКА показали, что всякий раз, когда случайно сгенерированный автомат был синхронизируем, его порог синхронизации оказывался намного меньше, чем граница из гипотезы Черни. Например, максимальное значение порога синхронизации, наблюдавшееся в [102] для синхронизируемых 100-автоматов с двумя входными буквами, составило 41 при том, что в ходе эксперимента было сгенерировано около миллиона таких автоматов. Напомним для сравнения, что гипотетическая верхняя граница для порога синхронизации синхронизируемых 100-автоматов составляет $99^2=9801$, а доказанная верхняя граница – $(100^3-100)/6=166\,650$. Таким образом, эксперименты показали, что, даже если гипотеза Черни в общем случае не выполнена, она с большим запасом верна для “почти всех” синхронизируемых автоматов. Это экспериментальное наблюдение нашло теоретическое обоснование в важных работах Сирила Нико [128] и М. В. Берлинкова и Марека Шикулы [28], которые в деталях обсуждаются во второй статье цикла. ЗаключениеДанная статья фокусировалась на алгоритмических и теоретико-сложностных аспектах синхронизации конечных детерминированных автоматов и на гипотезе Черни. Другие разделы теории синхронизируемых автоматов будут освещены во второй статье цикла. Она состоит из семи разделов, нумерация которых продолжается. В разделах 4 и 5 подробно обсуждаются два крупнейших достижения последних лет в теории синхронизируемых автоматов. Это найденное А. Н. Трахтманом [182] доказательство гипотезы Роя Л. Адлера, Л. Уэйна Гудвина и Бенджамина Вайса [1], известной под названием “Гипотеза о раскраске дорог”, и доказательство гипотезы Питера Камерона [38] о вероятности синхронизации случайного детерминированного автомата, полученное М. В. Берлинковым [26]. Раздел 6 посвящён глубоким связям между синхронизируемыми ДКА и примитивными неотрицательными матрицами. В трёх следующих разделах излагаются основные результаты о синхронизации других типов автоматов. В разделе 7 рассматриваются частичные детерминированные автоматы, в разделе 8 – недетерминированные автоматы, а в разделе 9 – различные другие автоматные модели. Заключительный раздел 10 содержит сводку основных открытых на сегодняшний день задач теории синхронизируемых автоматов. Я весьма признателен анонимному рецензенту за тщательный анализ первоначального варианта статьи. Конструктивные замечания и ценные предложения рецензента были учтены при доработке текста.
Цитирование в формате AMSBIB
\RBibitem{Vol22} |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|