Успехи математических наук
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Успехи математических наук, 2022, том 77, выпуск 5(467), страницы 53–130
DOI: https://doi.org/10.4213/rm10005
(Mi rm10005)
 

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Синхронизация конечных автоматов

М. В. Волков

Уральский федеральный университет
Список литературы:
Аннотация: Дан обзор современного состояния теории синхронизируемых автоматов в её части, относящейся к случаю полных детерминированных автоматов. Освещены алгоритмические и теоретико-сложностные аспекты, описаны имеющиеся результаты в направлении гипотезы Черни и методы их получения.
Библиография: 193 названия.
Ключевые слова: конечный автомат, синхронизируемость, алгоритм, вычислительная сложность, порог синхронизации, гипотеза Черни.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 19-11-50120
Министерство науки и высшего образования Российской Федерации FEUZ-2020-0016
Исследование выполнено при поддержке РФФИ (грант № 19-11-50120) и темы Госзадания FEUZ-2020-0016.
Поступила в редакцию: 31.08.2020
Англоязычная версия:
Russian Mathematical Surveys, 2022, Volume 77, Issue 5, Pages 819–891
DOI: https://doi.org/10.4213/rm10005e
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.713
MSC: Primary 03D15, 20F10; Secondary 20M35, 68Q25, 68Q45, 68Q70, 68R15

Введение

Синхронизация конечных автоматов – направление дискретной математики, первоначальные понятия которого очень прозрачны, поскольку непосредственно апеллируют к повседневной интуиции. В то же время это направление имеет разнообразные и зачастую неожиданные связи со многими разделами чистой математики и компьютерных наук, а также вполне практические приложения. Его особенная привлекательность состоит в том, что оно быстро приводит к интересным и трудным задачам, среди которых имеется целая россыпь замечательных по простоте формулировки открытых проблем. Идеальным примером здесь может служить гипотеза Черни, обсуждаемая в п. 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$

Состояние $a$$b$$b$$b$$a$$b$$b$$b$$a$
0123012301
1123012301
2230112301
3301223011

Вычисления, продемонстрированные в табл. 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$ для максимального префиксного кода
$$ \begin{equation} C:=\{000,0010,0011,010,0110,0111,10,110,111\}. \end{equation} \tag{1} $$

Максимальный префиксный код $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)

Передано$0\,0\,0\ \mid 0\,0\,1\,0\ \mid\mathbf{0\,1\,1\,1\mid\dots}$
Получено$1\,0\mid 0\,0\,0 \mid 1\,0 \mid\mathbf{0\,1\,1\,1\mid\dots}$
Передано$0\,0\,0\mid 0\,1\,1\,1 \mid 1\,1\,0\mid 0\,0\,1\,1 \mid 0\,0\,0 \mid 1\,0 \mid\mathbf{1\,1\,0\mid \dots}$
Получено$1\,0\mid 0\,0\,1\,1 \mid 1\,1\,1 \mid 0\,0\,0\mid 1\,1\,0 \mid 0\,0\,1\,0 \mid\mathbf{1\,1\,0\mid \dots}$
Передано$0\,0\,0\mid 0\,0\,0 \mid 1\,1\,1 \mid\mathbf{1\,0\mid \dots}$
Получено$1\,0\mid 0\,0\,0 \mid 0\,1\,1\, 1 \mid\mathbf{1\,0\mid \dots}$

Сходство терминологии намекает на родство синхронизированных кодов и синхронизируемых автоматов, и действительно, эти два понятия тесно связаны. В том специальном случае, который мы рассматриваем сейчас, их связь носит особенно непосредственный характер, как показывает следующий легко проверяемый результат.

Предложение 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\}$, определённую правилом

$$ \begin{equation} 0\mapsto 11,\quad 1\mapsto 12,\quad 2\mapsto 20. \end{equation} \tag{2} $$
Вычисляя итерации $\tau$ до $\tau^4$ (см. табл. 3), мы видим, что $\tau$ удовлетворяет условию совпадения с $k=4$, $m=7$.

Таблица 3.Подстановка, удовлетворяющая условию совпадения

$\begin{matrix} 0&\mapsto&11&\mapsto&1212&\mapsto&12201220&\mapsto&122020\mathbf{1}112202011 \\ 1&\mapsto&12&\mapsto&1220&\mapsto&12202011&\mapsto&122020\mathbf{1}120111212 \\ 2&\mapsto&20&\mapsto&2011&\mapsto&20111212&\mapsto&201112\mathbf{1}212201220 \end{matrix}$

Фредерик Мишель Деккинг [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]). Алгоритм состоит из набора тестов с ответами ДА/НЕТ. Подробное описание тестов дано в разделе второй статьи цикла, посвящённом синхронизации случайных автоматов; здесь же приведём три ключевых свойства набора:

Если какой-то из тестов не пройден, то ДКА может быть синхронизируемым, а может и не быть. В этой ситуации приходится запускать алгоритм Лю–Черни. Поэтому время работы алгоритма Берлинкова в наихудшем случае по-прежнему составляет $O(|Q|^2\,|\Sigma|)$. Однако, поскольку доля автоматов с $n$ состояниями, для которых требуется вызов алгоритма Лю–Черни, есть $O(1/n)$, среднее время работы алгоритма Берлинкова на ДКА, выбранном равномерно и случайно из всех ДКА с $n$ состояниями и фиксированным алфавитом, составляет $O(n)$. Подчеркнём, что описанный алгоритм не является вероятностным (хотя и опирается на статистические свойства случайных автоматов); он детерминирован и возвращает корректный ответ для любого ДКА.

П. С. Агеев [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 г. индийским информатиком А. В. Сриджитом, ранее не публиковался. Мы приводим доказательство с любезного разрешения автора.

Предложение 2.2. Задача DFA-SYNC является $\mathbf{NL}$-полной.

Доказательство. Ясно, что достаточно 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]).

Предложение 2.6. Задача SHORT-SW является $\mathbf{NP}$-полной.

Доказательство. Чтобы показать, что задача 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].

Следствие 2.2. Задача #SHORT-SW является $\#\mathbf{P}$-полной.

В литературе довольно часто можно встретить утверждения типа “задача нахождения длины кратчайшего синхронизирующего слова $\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] доказано следующее утверждение.

Предложение 2.7. Задача SHORTEST-SW является $\mathbf{DP}$-полной.

Теперь локализуем задачу нахождения порога синхронизации. Она ставится так:

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 точна.

Предложение 2.8. Задача COMPUTE-RT является $\mathbf{FP}^{\mathbf{NP}[\log]}$-полной.

Доказательство основано на сведе́нии от задачи 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], которое в наших обозначениях записывается как

$$ \begin{equation} (n-1)^2\leqslant\mathfrak{C}(n)\leqslant 2^n-n-1, \end{equation} \tag{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}$. Раскрыв этот определитель по первому столбцу, получим равенство
$$ \begin{equation*} \sum_{j=0}^{k}(-1)^jp(i_j)D(I'\setminus\{i_j\})=0. \end{equation*} \notag $$
Поскольку $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$. Поэтому
$$ \begin{equation*} |(I'\setminus\{i_j\})\setminus W|<|I\setminus W|, \end{equation*} \notag $$
и по предположению индукции любой многочлен $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$, приходим к анонсированной выше оценке
$$ \begin{equation} \mathfrak{C}(n)\leqslant\frac{n^3-n}{6}\,. \end{equation} \tag{7} $$

В литературе неравенство (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) можно улучшить до

$$ \begin{equation} \mathfrak{C}(n)\leqslant\frac{n^3-n}6-1. \end{equation} \tag{8} $$
Оценка (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}$ – произвольная функция такая, что

$$ \begin{equation} f(n)\geqslant f(n-m+1)+f(m)\quad\textit{при всех } n\geqslant m\geqslant 1. \end{equation} \tag{11} $$
Если у каждого сильно связного синхронизируемого ДКА из $\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}$. При этом

$$ \begin{equation*} |uv|=|u|+|v|=f(n-m+1)+f(m)\leqslant f(n) \end{equation*} \notag $$
согласно (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$. Отсюда следует, что
$$ \begin{equation*} |w|\leqslant 1+2+\cdots+(n-1)=\frac{n(n-1)}{2}\,. \end{equation*} \notag $$
Итак, $\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 позволяет строить синхронизирующие слова длины не больше
$$ \begin{equation} |w_{1/2}|+\frac{n(7n^2-6n-16)}{48}\,. \end{equation} \tag{12} $$
(Теперь читателю должно стать понятней происхождение слагаемого $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$-автомат и имеющее длину не больше

$$ \begin{equation*} \frac{85059n^3+90024n^2+196504n-10648}{511104}\,, \end{equation*} \notag $$
можно найти за полиномиальное от $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$:

$$ \begin{equation*} Pw^{-1}:=\{q\in Q\mid q \operatorname{.} w\in P\}. \end{equation*} \notag $$
Отметим, что $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. Сводка частичных результатов

Этот пункт носит справочный характер. В нём собраны основные результаты, устанавливающие справедливость ограничения гипотезы Черни на различные классы ДКА. В дополнение к этому перечислены классы автоматов, для которых гипотеза Черни не доказана, но известна квадратичная по числу состояний верхняя оценка для порога синхронизации. Некоторые из обсуждаемых в этом пункте результатов уже упоминалось выше; мы сочли уместным привести их и здесь для полноты сводного списка. Сведения, относящиеся к каждому классу автоматов, организованы в следующем формате:

В случаях, когда верхняя оценка равна нижней, т. е. ограничение функции Черни на соответствующий класс ДКА известно, к метке класса добавлен верхний индекс $\unicode{8224}$.

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}$ называется обобщённо монотонным, если он допускает цепочку конгруэнций

$$ \begin{equation*} \rho_0\subset\rho_1\subset\dots\subset\rho_\ell \end{equation*} \notag $$
такую, что $\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 содержит сводку основных открытых на сегодняшний день задач теории синхронизируемых автоматов.

Я весьма признателен анонимному рецензенту за тщательный анализ первоначального варианта статьи. Конструктивные замечания и ценные предложения рецензента были учтены при доработке текста.

Список литературы

1. R. L. Adler, L. W. Goodwyn, B. Weiss, “Equivalence of topological Markov shifts”, Israel J. Math., 27:1 (1977), 49–63  crossref  mathscinet  zmath
2. P. Ageev, “Implementation of the algorithm for testing an automaton for synchronization in linear expected time”, J. Autom. Lang. Comb., 24:2-4 (2019), 139–152  crossref  mathscinet  zmath
3. J. Almeida, S. Margolis, B. Steinberg, M. Volkov, “Representation theory of finite semigroups, semigroup radicals and formal language theory”, Trans. Amer. Math. Soc., 361:3 (2009), 1429–1461  crossref  mathscinet  zmath
4. J. Almeida, E. Rodaro, “Semisimple synchronizing automata and the Wedderburn–Artin theory”, Internat. J. Found. Comput. Sci., 27:2 (2016), 127–145  crossref  mathscinet  zmath
5. J. Almeida, B. Steinberg, “Matrix mortality and the Černý–Pin conjecture”, Developments in language theory, Lecture Notes in Comput. Sci., 5583, Springer, Berlin, 2009, 67–80  crossref  mathscinet  zmath
6. J. Almeida, M. V. Volkov, “Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety”, J. Algebra Appl., 2:2 (2003), 137–163  crossref  mathscinet  zmath
7. Д. С. Ананичев, “Порог аннуляции для частично монотонных автоматов”, Изв. вузов. Матем, 2010, № 1, 3–13  mathnet  mathscinet  zmath; англ. пер.: D. S. Ananichev, “The annulation threshold for partially monotonic automata”, Russian Math. (Iz. VUZ), 54:1 (2010), 1–9  crossref
8. D. S. Ananichev, V. V. Gusev, “Approximation of reset thresholds with greedy algorithms”, Fund. Inform., 145:3 (2016), 221–227  crossref  mathscinet  zmath
9. D. S. Ananichev, I. V. Petrov, M. V. Volkov, “Collapsing words: a progress report”, Internat. J. Found. Comput. Sci., 17:3 (2006), 507–518  crossref  mathscinet  zmath
10. D. S. Ananichev, M. V. Volkov, “Some results on Černý type problems for transformation semigroups”, Semigroups and languages, World Sci. Publ., River Edge, NJ, 2004, 23–42  crossref  mathscinet  zmath
11. D. S. Ananichev, M. V. Volkov, “Synchronizing monotonic automata”, Theoret. Comput. Sci., 327:3 (2004), 225–239  crossref  mathscinet  zmath
12. D. S. Ananichev, M. V. Volkov, “Synchronizing generalized monotonic automata”, Theoret. Comput. Sci., 330:1 (2005), 3–13  crossref  mathscinet  zmath
13. Д. С. Ананичев, М. В. Волков, В. В. Гусев, “Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. науч. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 9–39  mathnet  mathscinet  zmath; англ. пер.: D. S. Ananichev, M. V. Volkov, V. V. Gusev, “Primitive digraphs with large exponents and slowly synchronizing automata”, J. Math. Sci. (N. Y.), 192:3 (2013), 263–278  crossref
14. D. Ananichev, V. Vorel, “A new lower bound for reset threshold of binary synchronizing automata with sink”, J. Autom. Lang. Comb., 24:2-4 (2019), 153–164  crossref  mathscinet  zmath
15. J. Araújo, P. Cameron, B. Steinberg, “Between primitive and 2-transitive: synchronization and its friends”, EMS Surv. Math. Sci., 4:2 (2017), 101–184  crossref  mathscinet  zmath
16. F. Arnold, B. Steinberg, “Synchronizing groups and automata”, Theoret. Comput. Sci., 359:1-3 (2006), 101–110  crossref  mathscinet  zmath
17. У. Р. Эшби, Введение в кибернетику, ИЛ, М., 1959, 432 с.  mathscinet; пер. с англ.: W. R. Ashby, An introduction to cybernetics, Chapman and Hall, Ltd., London, 1956, ix+295 с.  mathscinet  zmath
18. M.-P. Béal, M. V. Berlinkov, D. Perrin, “A quadratic upper bound on the size of a synchronizing word in one-cluster automata”, Internat. J. Found. Comput. Sci., 22:2 (2011), 277–288  crossref  mathscinet  zmath
19. M.-P. Béal, D. Perrin, “A quadratic upper bound on the size of a synchronizing word in one-cluster automata”, Developments in language theory, Lecture Notes in Comput. Sci., 5583, Springer, Berlin, 2009, 81–90  crossref  mathscinet  zmath
20. Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, E. Shapiro, “DNA molecule provides a computing machine with both data and fuel”, Proc. Natl. Acad. Sci. USA, 100:5 (2003), 2191–2196  crossref  adsnasa
21. Y. Benenson, T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, E. Shapiro, “Programmable and autonomous computing machine made of biomolecules”, Nature, 414:6862 (2001), 430–434  crossref  adsnasa
22. M. V. Berlinkov, “On a conjecture by Carpi and D'Alessandro”, Internat. J. Found. Comput. Sci., 22:7 (2011), 1565–1576  crossref  mathscinet  zmath
23. M. V. Berlinkov, “Synchronizing quasi-Eulerian and quasi-one-cluster automata”, Internat. J. Found. Comput. Sci., 24:6 (2013), 729–745  crossref  mathscinet  zmath
24. M. V. Berlinkov, “Approximating the minimum length of synchronizing words is hard”, Theory Comput. Syst., 54:2 (2014), 211–223  crossref  mathscinet  zmath
25. M. V. Berlinkov, “On two algorithmic problems about synchronizing automata”, Developments in language theory, Lecture Notes in Comput. Sci., 8633, Springer, Cham, 2014, 61–67  crossref  mathscinet  zmath
26. M. V. Berlinkov, “On the probability of being synchronizable”, Algorithms and discrete applied mathematics, Lecture Notes in Comput. Sci., 9602, Springer, Cham, 2016, 73–84  crossref  mathscinet  zmath
27. M. V. Berlinkov, R. Ferens, M. Szykuła, “Preimage problems for deterministic finite automata”, J. Comput. System Sci., 115 (2021), 214–234  crossref  mathscinet  zmath
28. M. V. Berlinkov, M. Szykuła, “Algebraic synchronization criterion and computing reset words”, Inform. Sci., 369 (2016), 718–730  crossref  zmath
29. J. Berstel, D. Perrin, C. Reutenauer, Codes and automata, Encyclopedia Math. Appl., 129, Cambridge Univ. Press, Cambridge, 2010, xiv+619 pp.  crossref  mathscinet  zmath
30. M. T. Biskup, Error resilience in compressed data – selected topics, Ph.D. thesis, Inst. of Informatics, Univ. of Warsaw, 2008, 136 pp., \par http://www.mimuw.edu.pl/sites/default/files/marek_biskup_mb-praca.pdf
31. M. T. Biskup, “Guaranteed synchronization of Huffman codes”, Data compression conference (DCC 2008) (Snowbird, UT, 2008), IEEE, 2008, 462–471  crossref
32. M. T. Biskup, W. Plandowski, “Guaranteed synchronization of Huffman codes with known position of decoder”, Data compression conference (DCC 2009) (Snowbird, UT, 2009), IEEE, 2009, 33–42  crossref
33. M. T. Biskup, W. Plandowski, “Shortest synchronizing strings for {H}uffman codes”, Theoret. Comput. Sci., 410:38-40 (2009), 3925–3941  crossref  mathscinet  zmath
34. S. Bogdanović, B. Imreh, M. Ćirić, T. Petković, “Directable automata and their generalizations: a survey”, Novi Sad J. Math., 29:2 (1999), 29–69  mathscinet  zmath
35. P. Bonizzoni, N. Jonoska, “Existence of constants in regular splicing languages”, Inform. and Comput., 242 (2015), 340–353  crossref  mathscinet  zmath
36. V. Boppana, S. P. Rajan, K. Takayama, M. Fujita, “Model checking based on sequential ATPG”, Computer aided verification, Lecture Notes in Comput. Sci., 1633, Springer-Verlag, Berlin, 1999, 418–430  crossref  mathscinet  zmath
37. R. A. Brualdi, H. J. Ryser, Combinatorial matrix theory, Encyclopedia Math. Appl., 39, Cambridge Univ. Press, Cambridge, 1991, x+367 pp.  crossref  mathscinet  zmath
38. P. J. Cameron, “Dixon's theorem and random synchronization”, Discrete Math., 313:11 (2013), 1233–1236  crossref  mathscinet  zmath
39. R. M. Capocelli, L. Gargano, U. Vaccaro, “On the characterization of statistically synchronizable variable-length codes”, IEEE Trans. Inform. Theory, 34:4 (1988), 817–825  crossref  mathscinet  zmath
40. A. Carpi, F. D'Alessandro, “Strongly transitive automata and the Černý conjecture”, Acta Inform., 46:8 (2009), 591–607  crossref  mathscinet  zmath
41. A. Carpi, F. D'Alessandro, “The synchronization problem for locally strongly transitive automata”, Mathematical foundations of computer science 2009, Lecture Notes in Comput. Sci., 5734, Springer, Berlin, 2009, 211–222  crossref  mathscinet  zmath
42. A. Carpi, F. D'Alessandro, “Independent sets of words and the synchronization problem”, Adv. in Appl. Math., 50:3 (2013), 339–355  crossref  mathscinet  zmath
43. A. Carpi, F. D'Alessandro, “Locally strongly transitive automata in the Černý conjecture and related problems”, J. Autom. Lang. Comb., 24:2-4 (2019), 165–184  crossref  mathscinet  zmath
44. J. Černý, “Poznámka k homogénnym eksperimentom s konečnými automatami”, Mat.-Fyz. Časopis Sloven. Akad. Vied., 14:3 (1964), 208–216  mathscinet  zmath; англ. пер. J. Černý, “A note on homogeneous experiments with finite automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 123–132  crossref  mathscinet  zmath
45. J. Černý, A. Pirická, B. Rosenauerová, “On directable automata”, Kybernetika (Prague), 7:4 (1971), 289–298  mathscinet  zmath
46. Yui-Bin Chen, D. J. Ierardi, “The complexity of oblivious plans for orienting and distinguishing polygonal parts”, Algorithmica, 14:5 (1995), 367–397  crossref  mathscinet  zmath
47. A. Cherubini, “Synchronizing and collapsing words”, Milan J. Math., 75:1 (2007), 305–321  crossref  mathscinet
48. A. Cherubini, A. Frigeri, Zuhua Liu, “Composing short 3-compressing words on a 2-letter alphabet”, Discrete Math. Theor. Comput. Sci., 19:1 (2017), 17, 35 pp.  crossref  mathscinet  zmath
49. A. Cherubini, A. Kisielewicz, “Collapsing words, permutation conditions and coherent colorings of trees”, Theoret. Comput. Sci., 410:21-23 (2009), 2135–2147  crossref  mathscinet  zmath
50. A. Cherubini, A. Kisielewicz, “Recognizing 3-collapsing words over a binary alphabet”, Theoret. Comput. Sci., 629 (2016), 64–79  crossref  mathscinet  zmath
51. A. Cherubini, A. Kisielewicz, B. Piochi, “On the length of shortest 2-collapsing words”, Discrete Math. Theor. Comput. Sci., 11:1 (2009), 33–44  crossref  mathscinet  zmath
52. K. Chmiel, A. Roman, “COMPAS – a computing package for synchronization”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6482, Springer, Berlin, 2011, 79–86  crossref  mathscinet  zmath
53. Hyunwoo Cho, Seh-Woong Jeong, F. Somenzi, C. Pixley, “Multiple observation time single reference test generation using synchronizing sequences”, 1993 European conference on design automation with the European event in ASIC design (Paris, 1993), IEEE, 1993, 494–498  crossref
54. Hyunwoo Cho, Seh-Woong Jeong, F. Somenzi, C. Pixley, “Synchronizing sequences and symbolic traversal techniques in test generation”, J. Electronic Testing, 4 (1993), 19–31  crossref
55. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн, Алгоритмы: построение и анализ, 3-е изд., Вильямс, М., 2011, 1324 с.; пер. с англ.: Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, 3rd ed., MIT Press, Cambridge, MA, 2009, xx+1292 с.  mathscinet  zmath
56. Zhen He Cui, Yong He, Shi Yuan Sun, “Synchronizing bounded partially ordered automata”, (Chinese), Chinese J. Comput., 42:3 (2019), 610–623  mathscinet
57. M. de Bondt, A short proof of a theorem of J.-E. Pin, 2018, 12 pp., arXiv: 1811.11660
58. M. de Bondt, H. Don, H. Zantema, “DFAs and PFAs with long shortest synchronizing word length”, Developments in language theory, Lecture Notes in Comput. Sci., 10396, Springer, Cham, 2017, 122–133  crossref  mathscinet  zmath
59. F. M. Dekking, “The spectrum of dynamical systems arising from substitutions of constant length”, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 41:3 (1978), 221–239  crossref  mathscinet  zmath
60. H. Don, H. Zantema, “Finding DFAs with maximal shortest synchronizing word length”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 10168, Springer, Cham, 2017, 249–260  crossref  mathscinet  zmath
61. H. Don, H. Zantema, “Counting symbol switches in synchronizing automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 253–286  crossref  mathscinet  zmath
62. L. Dubuc, “Sur les automates circulaires et la conjecture de Černý”, RAIRO Inform. Théor. Appl., 32:1-3 (1998), 21–34  crossref  mathscinet
63. M. Dżyga, R. Ferens, V. V. Gusev, M. Szykuła, “Attainable values of reset thresholds”, 42nd international symposium on mathematical foundations of computer science, LIPIcs. Leibniz Int. Proc. Inform., 83, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, 40, 14 pp.  crossref  mathscinet  zmath
64. D. Eppstein, “Reset sequences for monotonic automata”, SIAM J. Comput., 19:3 (1990), 500–510  crossref  mathscinet  zmath
65. D. Eppstein, J.-C. Falmagne, “Algorithms for media”, Discrete Appl. Math., 156:8 (2008), 1308–1320  crossref  mathscinet  zmath
66. H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov, P. Wolf, “Computational complexity of synchronization under regular constraints”, 44th international symposium on mathematical foundations of computer science, LIPIcs. Leibniz Int. Proc. Inform., 138, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, 63, 14 pp.  crossref  mathscinet  zmath
67. H. Fernau, P. Heggernes, Y. Villanger, “A multi-parameter analysis of hard problems on deterministic finite automata”, J. Comput. System Sci., 81:4 (2015), 747–765  crossref  mathscinet  zmath
68. H. Fernau, A. Krebs, “Problems on finite automata and the exponential time hypothesis”, Algorithms (Basel), 10:1 (2017), 24, 25 pp.  crossref  mathscinet  zmath
69. M. A. Fischler, M. Tannenbaum, “Synchronizing and representation problems for sequential machines with masked outputs”, 11th annual symposium on switching and automata theory (SWAT 1970), IEEE, 1970, 97–103  crossref
70. P. Frankl, “An extremal problem for two families of sets”, European J. Combin., 3:2 (1982), 125–127  crossref  mathscinet  zmath
71. D. Frettlöh, B. Sing, “Computing modular coincidences for substitution tilings and point sets”, Discrete Comput. Geom., 37:3 (2007), 381–407  crossref  mathscinet  zmath
72. A. Frigeri, E. Rodaro, “Missing factors of ideals and synchronizing automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 309–320  crossref  mathscinet  zmath
73. P. Gawrychowski, Complexity of shortest synchronizing word, preprint, 2008
74. P. Gawrychowski, D. Straszak, “Strong inapproximability of the shortest reset word”, Mathematical foundations of computer science 2015, Part I, Lecture Notes in Comput. Sci., 9234, Springer, Heidelberg, 2015, 243–255  crossref  mathscinet  zmath
75. M. Gerbush, B. Heeringa, “Approximating minimum reset sequences”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6482, Springer, Berlin, 2011, 154–162  crossref  mathscinet  zmath
76. A. Gill, “State-identification experiments in finite automata”, Information and Control, 4:2-3 (1961), 132–154  crossref  mathscinet  zmath
77. С. Гинзбург, “О длине кратчайшего однородного эксперимента, устанавливающего конечные состояния машины”, Киберн. сб., 3, ИЛ, М., 1961, 167–186  zmath; пер. с англ.: S. Ginsburg, “On the length of the smallest uniform experiment which distinguishes the terminal states of a machine”, J. Assoc. Comput. Mach., 5:3 (1958), 266–280  crossref  mathscinet  zmath
78. S. Ginsburg, An introduction to mathematical machine theory, Addison-Wesley Publishing Co., Inc., Reading, MA–Palo Alto, CA–London, 1962, ix+147 pp.  mathscinet  zmath
79. K. Y. Goldberg, “Orienting polygonal parts without sensors”, Algorithmica, 10:2-4 (1993), 201–225  crossref  mathscinet  zmath
80. F. Gonze, V. V. Gusev, R. M. Jungers, B. Gerencsér, M. V. Volkov, “On the interplay between Černý and {B}abai's conjectures”, Internat. J. Found. Comput. Sci., 30:1 (2019), 93–114  crossref  mathscinet  zmath
81. F. Gonze, R. M. Jungers, A. N. Trahtman, “A note on a recent attempt to improve the Pin–Frankl bound”, Discrete Math. Theor. Comput. Sci., 17:1 (2015), 307–308  crossref  mathscinet  zmath
82. P. Goralčík, V. Koubek, “Rank problems for composite transformations”, Internat. J. Algebra Comput., 5:3 (1995), 309–316  crossref  mathscinet  zmath
83. Р. Грэхем, Д. Кнут, О. Паташник, Конкретная математика. Основание информатики, 2-е изд., испр., Мир, Бином. Лаборатория знаний, М., 2006, 703 с.; пер. с англ.: R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics. A foundation for computer science, 2nd ed., Addison-Wesley Publ. Co., Reading, MA, 2006, xiv+657 с.  mathscinet  zmath
84. M. Grech, A. Kisielewicz, “The Černý conjecture for automata respecting intervals of a directed graph”, Discrete Math. Theor. Comput. Sci., 15:3 (2013), 61–72  crossref  mathscinet  zmath
85. M. Grech, A. Kisielewicz, “Synchronizing sequences for road colored digraphs”, Discrete Appl. Math., 285 (2020), 128–140  crossref  mathscinet  zmath
86. V. V. Gusev, “Lower bounds for the length of reset words in Eulerian automata”, Reachability problems, Lecture Notes in Comput. Sci., 6945, Springer, Berlin, 2011, 180–190  crossref  zmath
87. V. V. Gusev, R. M. Jungers, D. Průša, “Dynamics of the independence number and automata synchronization”, Developments in language theory, Lecture Notes in Comput. Sci., 11088, Springer, Cham, 2018, 379–391  crossref  mathscinet  zmath
88. V. V. Gusev, M. I. Maslennikova, E. V. Pribavkina, “Principal ideal languages and synchronizing automata”, Fund. Inform., 132:1 (2014), 95–108  crossref  mathscinet  zmath
89. V. V. Gusev, E. V. Pribavkina, “On codeword lengths guaranteeing synchronization”, Combinatorics on words, Lecture Notes in Comput. Sci., 11682, Springer, Cham, 2019, 207–216  crossref  mathscinet  zmath
90. J. Håstad, “Clique is hard to approximate within $n^{1-\varepsilon}$ ”, Acta Math., 182:1 (1999), 105–142  crossref  mathscinet  zmath
91. S. Hoffmann, “On a class of constrained synchronization problems in NP”, Proceedings of the 21st Italian conference on theoretical computer science (Ischia, 2020), CEUR Workshop Proceedings, 2756, 2020, 145–157 http://ceur-ws.org/Vol-2756/
92. S. Hoffmann, “Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 12638, Springer, Cham, 2021, 305–317  crossref  mathscinet  zmath
93. S. Hoffmann, “State complexity of the set of synchronizing words for circular automata and automata over binary alphabets”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 12638, Springer, Cham, 2021, 318–330  crossref  mathscinet  zmath
94. S. Hoffmann, “Constrained synchronization and subset synchronization problems for weakly acyclic automata”, Developments in language theory, Lecture Notes in Comput. Sci., 12811, Springer, Cham, 2021, 204–216  crossref  mathscinet  zmath
95. S. Hoffmann, “Computational complexity of synchronization under sparse regular constraints”, Fundamentals of computation theory, Lecture Notes in Comput. Sci., 12867, Springer, Cham, 2021, 272–286  crossref  mathscinet  zmath
96. S. Hoffmann, “Ideal separation and general theorems for constrained synchronization and their application to small constraint automata”, Computing and combinatorics, Lecture Notes in Comput. Sci., 13025, Springer, Cham, 2021, 176–188  crossref  mathscinet  zmath
97. S. Hoffmann, “Constrained synchronization and commutativity”, Theoret. Comput. Sci., 890 (2021), 147–170  crossref  mathscinet  zmath
98. H. J{ü}rgensen, “Synchronization”, Inform. and Comput., 206:9-10 (2008), 1033–1044  crossref  mathscinet  zmath
99. J. Kari, “A counter example to a conjecture concerning synchronizing words in finite automata”, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 73 (2001), 146  mathscinet  zmath
100. J. Kari, “Synchronizing finite automata on Eulerian digraphs”, Theoret. Comput. Sci., 295:1-3 (2003), 223–232  crossref  mathscinet  zmath
101. J. Kari, M. Volkov, “Černý's conjecture and the road colouring problem”, Handbook of automata theory, Ch. 15, v. I, Theoretical foundations, EMS Press, Berlin, 2021, 525–565  crossref  mathscinet  zmath
102. A. Kisielewicz, J. Kowalski, M. Szykuła, “Computing the shortest reset words of synchronizing automata”, J. Comb. Optim., 29:1 (2015), 88–124  crossref  mathscinet  zmath
103. A. Kisielewicz, J. Kowalski, M. Szykuła, “Experiments with synchronizing automata”, Implementation and application of automata, Lecture Notes in Comput. Sci., 9705, Springer, Cham, 2016, 176–188  crossref  mathscinet  zmath
104. A. Kisielewicz, M. Szykuła, “Generating small automata and the Černý conjecture”, Implementation and application of automata, Lecture Notes in Comput. Sci., 7982, Springer, Heidelberg, 2013, 340–348  crossref  mathscinet  zmath
105. A. Kisielewicz, M. Szykuła, “Synchronizing automata with extremal properties”, Mathematical foundations of computer science 2015, Part 1, Lecture Notes in Comput. Sci., 9234, Springer, Heidelberg, 2015, 331–343  crossref  mathscinet  zmath
106. С. К. Клини, “Представление событий в нервных сетях и конечных автоматах”, Автоматы, Сб. ст., ИЛ, М., 1956, 15–67; пер. с англ.: S. C. Kleene, “Representation of events in nerve nets and finite automata”, Automata studies, Ann. of Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956, 3–41  crossref  mathscinet  zmath
107. А. А. Клячко, И. К. Рысцов, М. А. Спивак, “Об одной экстремальной комбинаторной задаче, связанной с оценкой длины возвратного слова в автомате”, Кибернетика, 25:2 (1987), 16–20  mathscinet  zmath; англ. пер.: A. A. Klyachko, I. K. Rystsov, M. A. Spivak, “An extremal combinatorial problem associated with the bound of the length of a synchronizing word in an automaton”, Cybernetics, 23:2 (1987), 165–171  crossref
108. Z. Kohavi, J. Winograd, “Bounds on the length of synchronizing sequences and the order of information losslessness”, Theory of machines and computations, Academic Press, New York, 1971, 197–206  crossref  mathscinet  zmath
109. Z. Kohavi, J. Winograd, “Establishing certain bounds concerning finite automata”, J. Comput. System Sci., 7:3 (1973), 288–299  crossref  mathscinet  zmath
110. D. Kozen, “Lower bounds for natural proof systems”, 18th annual symposium on foundations of computer science (Providence, RI, 1977), IEEE Comput. Sci., Long Beach, CA, 1977, 254–266  crossref  mathscinet  zmath
111. M. W. Krentel, “The complexity of optimization problems”, J. Comput. System Sci., 36:3 (1988), 490–509  crossref  mathscinet  zmath
112. A. E. Laemmel, A general class of discrete codes and certain of their properties, Res. rep. R-459-55, PIB-389, Microwave Research Inst., Polytechnic Inst., Brooklyn, NY, 1956
113. A. E. Laemmel, Study on application of coding theory, Tech. rep. PIBMRI-895.5-63, Dept. Electrophysics, Microwave Research Inst., Polytechnic Inst., Brooklyn, NY, 1963
114. A. E. Laemmel, B. Rudner, Study of the application of coding theory, Tech. rep. PIBEP-69-034, Dept. Electrophysics, Polytechnic Inst., Brooklyn, Farmingdale, NY, 1969
115. В. И. Левенштейн, “Самонастраивающиеся автоматы для декодирования сообщений”, Докл. АН СССР, 141:6 (1961), 1320–1323  mathnet  mathscinet  zmath; англ. пер.: V. I. Levenshteĭn, “Self-adaptive automata for decoding messages”, Soviet Physics Dokl., 6 (1961), 1042–1045
116. Chung Laung Liu, “Determination of the final state of an automaton whose initial state is unknown”, IEEE Trans. Electronic Computers, EC-12:6 (1963), 918–920  crossref
117. Chung Laung Liu, Some memory aspects of finite automata, Tech. rep. 411, Research Lab. Electronics, Massachusetts Inst., MIT Res. Lab. Electronics, Cambridge, MA, 1963, 71 pp. http://hdl.handle.net/1721.1/4414
118. P. V. Martugin, “A series of slowly synchronizing automata with a zero state over a small alphabet”, Inform. and Comput., 206:9-10 (2008), 1197–1203  crossref  mathscinet  zmath
119. M. Maslennikova, “Reset complexity of ideal languages over a binary alphabet”, Internat. J. Found. Comput. Sci., 30:6-7 (2019), 1177–1196  crossref  mathscinet  zmath
120. M. Maslennikova, E. Rodaro, “Representation of (left) ideal regular languages by synchronizing automata”, Computer science – theory and applications, Lecture Notes in Comput. Sci., 9139, Springer, Cham, 2015, 325–338  crossref  mathscinet  zmath
121. M. Maslennikova, E. Rodaro, “Trim strongly connected synchronizing automata and ideal languages”, Fund. Inform., 162:2-3 (2018), 183–203  crossref  mathscinet  zmath
122. A. Mateescu, A. Salomaa, “Many-valued truth functions, Černý's conjecture, and road coloring”, Current trends in theoretical computer science. Entering the 21th century, World Sci. Publ., River Edge, NJ, 2001, 693–707  crossref  mathscinet  zmath
123. Ю. Т. Медведев, “О классе событий, допускающих представление в конечном автомате”, Автоматы, Сб. ст., ИЛ, М., 1956, 385–401
124. E. H. Moore, “On certain crinkly curves”, Trans. Amer. Math. Soc., 1:1 (1900), 72–90  crossref  mathscinet  zmath; “Errata”, Trans. Amer. Math. Soc., 1 (1900), 507  crossref  mathscinet
125. Э. Ф. Мур, “Умозрительные эксперименты с последовательностными машинами”, Автоматы, Сб. ст., ИЛ, М., 1956, 179–210; пер. с англ.: E. F. Moore, “Gedanken-experiments on sequential machines”, Automata studies, Ann. of Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956, 129–153  crossref  mathscinet  zmath
126. B. K. Natarajan, “An algorithmic approach to the automated design of parts orienters”, 27th annual symposium on foundations of computer science (SFCS 1986) (Toronto, ON, 1986), IEEE, 1986, 132–142  crossref
127. B. K. Natarajan, “Some paradigms for the automated design of parts feeders”, Int. J. Robot. Res., 8:6 (1989), 98–109  crossref
128. C. Nicaud, “The Černý conjecture holds with high probability”, J. Autom. Lang. Comb., 24:2-4 (2019), 343–365  crossref  mathscinet  zmath
129. J. Olschewski, M. Ummels, “The complexity of finding reset words in finite automata”, Mathematical foundations of computer science 2010, Lecture Notes in Comput. Sci., 6281, Springer, Berlin, 2010, 568–579  crossref  mathscinet  zmath  adsnasa
130. C. H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Co., Reading, MA, 1994, xvi+523 pp.  mathscinet  zmath
131. C. H. Papadimitriou, M. Yannakakis, “The complexity of facets (and some facets of complexity)”, J. Comput. System Sci., 28:2 (1984), 244–259  crossref  mathscinet  zmath
132. J.-E. Pin, Le problème de la synchronisation et la conjecture de Černý, Thèse de 3ème cycle, Univ. Paris VI, 1978
133. J.-E. Pin, “Sur un cas particulier de la conjecture de Cerny”, Automata, languages and programming (Udine, 1978), Lecture Notes in Comput. Sci., 62, Springer, Berlin–New York, 1978, 345–352  crossref  mathscinet  zmath
134. J.-E. Pin, “Utilisation de l'algèbre linéaire en théorie des automates”, Actes du 1er colloque AFCET-SMF de mathématiques appliquées (Palaiseau, 1978), AFCET, 1978, 85–92 https://hal.archives-ouvertes.fr/hal-00340773
135. J. E. Pin, “On two combinatorial problems arising from automata theory”, Combinatorial mathematics (Marseille–Luminy, 1981), North-Holland Math. Stud., 75, Ann. Discrete Math., 17, North-Holland, Amsterdam, 1983, 535–548  crossref  mathscinet  zmath
136. C. Pixley, S.-W. Jeong, G. D. Hachtel, “Exact calculation of synchronizing sequences based on binary decision diagrams”, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 13:8 (1994), 1024–1034  crossref
137. R. Pöschel, M. V. Sapir, N. V. Sauer, M. G. Stone, M. V. Volkov, “Identities in full transformation semigroups”, Algebra Universalis, 31:4 (1994), 580–588  crossref  mathscinet  zmath
138. Е. В. Прибавкина, “Медленно синхронизируемые автоматы с нулем и непокрывающие множества”, Матем. заметки, 90:3 (2011), 422–430  mathnet  crossref  mathscinet  zmath; англ. пер.: E. V. Pribavkina, “Slowly synchronizing automata with zero and noncomplete sets”, Math. Notes, 90:3 (2011), 411–417  crossref
139. E. V. Pribavkina, E. Rodaro, “Synchronizing automata with finitely many minimal synchronizing words”, Inform. and Comput., 209:3 (2011), 568–579  crossref  mathscinet  zmath
140. N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Math., 1794, eds. V. Berthé, S. Ferenczi, C. Mauduit, A. Siegel, Springer-Verlag, Berlin, 2002  crossref  mathscinet  zmath
141. M. O. Rabin, D. Scott, “Finite automata and their decision problems”, IBM J. Res. Develop., 3:2 (1959), 114–125  crossref  mathscinet  zmath
142. J. L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Lecture Ser. Math. Appl., 30, Oxford Univ. Press, Oxford, 2005, xvi+243 pp.  mathscinet  zmath
143. A. S. Rao, K. Y. Goldberg, “Manipulating algebraic parts in the plane”, IEEE Trans. Robotics Autom., 11:4 (1995), 598–602  crossref
144. R. Reis, E. Rodaro, “Ideal regular languages and strongly connected synchronizing automata”, Theoret. Comput. Sci., 653 (2016), 97–107  crossref  mathscinet  zmath
145. June-Kyung Rho, F. Somenzi, C. Pixley, “Minimum length synchronizing sequences of finite state machine”, 30th ACM/IEEE design automation conference (Dallas, TX, 1993), ACM, New York, NY, 1993, 463–468  crossref
146. E. Rodaro, “Strongly connected synchronizing automata and the language of minimal reset words”, Adv. in Appl. Math., 99 (2018), 158–173  crossref  mathscinet  zmath
147. E. Rodaro, “A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number”, J. Algebraic Combin., 50:3 (2019), 237–253  crossref  mathscinet  zmath
148. A. Roman, M. Szykuła, “Forward and backward synchronizing algorithms”, Expert Syst. Appl., 42:24 (2015), 9512–9527  crossref
149. И. К. Рысцов, “Оценка длины ядерного слова для конечного автомата”, Автоматы, Межвуз. науч. сб., т. 2, Сарат. гос. ун-т, Саратов, 1977, 43–48  mathscinet  zmath
150. И. К. Рысцов, “О минимизации синхронизирующих слов для конечных автоматов”, Теоретические вопросы проектирования вычислительных систем, АН УССР, Науч. совет по пробл. “Кибернетика”, Ин-т кибернетики, Киев, 1980, 75–82  mathscinet  zmath
151. I. K. Rystsov, “Polynomial complete problems in automata theory”, Inform. Process. Lett., 16:3 (1983), 147–151  crossref  mathscinet  zmath
152. И. К. Рысцов, “О ранге конечного автомата”, Кибернетика и системный анализ, 28:3 (1992), 3–10  mathscinet  zmath; англ. пер.: I. K. Rystsov, “Rank of a finite automaton”, Cybernet. Systems Anal., 28:3 (1992), 323–328  crossref
153. И. К. Рысцов, “Возвратные слова для разрешимых автоматов”, Кибернетика и системный анализ, 30:6 (1994), 21–26  mathscinet  zmath; англ. пер.: I. K. Rystsov, “Resetting words for decidable automata”, Cybernet. Systems Anal., 30:6 (1992), 807–811  crossref
154. И. К. Рысцов, “Почти оптимальная оценка длины возвратного слова для регулярных автоматов”, Кибернетика и системный анализ, 31:5 (1995), 40–48  mathscinet  zmath; англ. пер.: I. K. Rystsov, “Almost optimal bound of reccurent word length for regular automata”, Cybernet. Systems Anal., 31:5 (1995), 669–674  crossref
155. I. K. Rystsov, “Quasioptimal bound for the length of reset words for regular automata”, Acta Cybernet., 12:2 (1995), 145–152  mathscinet  zmath
156. I. Rystsov, “Exact linear bound for the length of reset words in commutative automata”, Publ. Math. Debrecen, 48:3-4, suppl. (1996), 405–409  mathscinet  zmath
157. I. Rystsov, “Reset words for commutative and solvable automata”, Theoret. Comput. Sci., 172:1-2 (1997), 273–279  crossref  mathscinet  zmath
158. И. К. Рысцов, “О длине возвратных слов для автоматов с простыми идемпотентами”, Кибернетика и системный анализ, 36:3 (2000), 32–39  mathscinet  zmath; англ. пер.: I. K. Rystsov, “Estimation of the length of reset words for automata with simple idempotents”, Cybernet. Systems Anal., 36:3 (2000), 339–344  crossref
159. I. K. Рисцов, “Проблема Чернi для автоматiв iз простими iдемпотентами”, Кiбернетика та системний аналiз, 58:1 (2022), 3–10  mathscinet  zmath; англ. пер.: I. K. Rystsov, “Cerny's conjecture for automata with simple idempotents”, Cybernet. Systems Anal., 58:1 (2022), 1–7  crossref
160. A. Ryzhikov, “Synchronization problems in automata without non-trivial cycles”, Theoret. Comput. Sci., 787 (2019), 77–88  crossref  mathscinet  zmath
161. A. Ryzhikov, M. Szykula, “Finding short synchronizing words for prefix codes”, 43rd international symposium on mathematical foundations of computer science (Liverpool, UK, 2018), LIPIcs. Leibniz Int. Proc. Inform., 117, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, 21, 14 pp.  crossref  mathscinet  zmath
162. A. Salomaa, “Compositions over a finite domain: from completeness to synchronizable automata”, A half-century of automata theory. Celebration and inspiration (London, ON, 2000), World Sci. Publ., River Edge, NJ, 2001, 131–143  crossref  mathscinet  zmath
163. A. Salomaa, “Generation of constants and synchronization of finite automata”, J. UCS, 8:2 (2002), 332–347  mathscinet  zmath
164. A. Salomaa, “Synchronization of finite automata: contributions to an old problem”, The essence of computation. Complexity, analysis, transformation, Essays dedicated to N. D. Jones [on occasion of his 60th birthday], Lecture Notes in Comput. Sci., 2566, Springer, Berlin, 2002, 37–59  crossref  zmath
165. A. Salomaa, “Composition sequences for functions over a finite domain”, Theoret. Comput. Sci., 292:1 (2003), 263–281  crossref  mathscinet  zmath
166. S. Sandberg, “Homing and synchronizing sequences”, Model-based testing of reactive systems. Advanced lectures, Lecture Notes in Comput. Sci., 3472, Springer-Verlag, Berlin, 2005, 5–33  crossref  mathscinet  zmath
167. M. Schützenberger, “On an application of semi groups methods to some problems in coding”, IRE Trans. Inform. Theory, 2:3 (1956), 47–60  crossref
168. Y. Shitov, “An improvement to a recent upper bound for synchronizing words of finite automata”, J. Autom. Lang. Comb., 24:2-4 (2019), 367–373  crossref  mathscinet  zmath
169. E. Skvortsov, E. Tipikin, “Experimental study of the shortest reset word of random automata”, Implementation and application of automata, Lecture Notes in Comput. Sci., 6807, Springer, Heidelberg, 2011, 290–298  crossref  mathscinet  zmath
170. P. H. Starke, “Eine Bemerkung über homogene Experimente”, Elektron. Informationsverarb. Kybernet., 2 (1966), 257–259  zmath; англ. пер.: P. H. Starke, “A remark about homogeneous experiments”, J. Autom. Lang. Comb., 24:2-4 (2019), 133–137  crossref  mathscinet  zmath
171. P. H. Starke, Abstrakte Automaten, VEB Deutscher Verlag der Wissenschaften, Berlin, 1969, 392 с.  mathscinet  zmath; англ. пер. P. H. Starke, Abstract automata, North-Holland Publishing Co., Amsterdam–London; American Elsevier Publishing Co., Inc., New York, 1972, 419 с.  mathscinet  zmath
172. B. Steinberg, “Černý's conjecture and group representation theory”, J. Algebraic Combin., 31 (2010), 83–109  crossref  mathscinet  zmath
173. B. Steinberg, “The averaging trick and the Černý conjecture”, Internat. J. Found. Comput. Sci., 22:7 (2011), 1697–1706  crossref  mathscinet  zmath
174. B. Steinberg, “The Černý conjecture for one-cluster automata with prime length cycle”, Theoret. Comput. Sci., 412:39 (2011), 5487–5491  crossref  mathscinet  zmath
175. M. Suomalainen, A. Q. Nilles, S. M. LaValle, “Virtual reality for robots”, 2020 IEEE/RSJ international conference on intelligent robots and systems (IROS) (Las Vegas, NV, 2020), IEEE, 2020, 11458–11465  crossref
176. M. Szykuła, Algorithms for synchronizing automata, Ph.D. thesis, Inst. of Computer Science, Univ. of Wrocław, 2014
177. M. Szykuła, “Improving the upper bound on the length of the shortest reset word”, 35th symposium on theoretical aspects of computer science, LIPIcs. Leibniz Int. Proc. Inform., 96, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, 56, 13 pp.  crossref  mathscinet  zmath
178. M. Szykuła, V. Vorel, “An extremal series of {E}ulerian synchronizing automata”, Developments in language theory, Lecture Notes in Comput. Sci., 9840, Springer, Berlin, 2016, 380–392  crossref  mathscinet  zmath
179. A. N. Trahtman, “An efficient algorithm finds noticeable trends and examples concerning the Černý conjecture”, Mathematical foundations of computer science 2006, Lecture Notes in Comput. Sci., 4162, Springer, Berlin, 2006, 789–800  crossref  mathscinet  zmath
180. A. N. Trahtman, “The Černý conjecture for aperiodic automata”, Discrete Math. Theor. Comput. Sci., 9:2 (2007), 3–10  crossref  mathscinet  zmath
181. A. Trahtman, “Some aspects of synchronization of DFA”, J. Comput. Sci. Tech., 23:5 (2008), 719–727  crossref  mathscinet
182. A. N. Trahtman, “The road coloring problem”, Israel J. Math., 172:1 (2009), 51–60  crossref  mathscinet  zmath
183. A. N. Trahtman, “Modifying the upper bound on the length of minimal synchronizing word”, Fundamentals of computation theory, Lecture Notes in Comput. Sci., 6914, Springer, Heidelberg, 2011, 173–180  crossref  mathscinet  zmath
184. A. N. Trahtman, The Černy conjecture, 2022 (v1 – 2012), 14 pp., arXiv: 1202.4626
185. A. N. Trahtman, The length of a minimal synchronizing word and the Černy conjecture, 2021 (v1 – 2014), 14 pp., arXiv: 1405.2435
186. A. N. Trahtman, Cerny–Starke conjecture from the sixties of XX century, 2021 (v1 – 2020), 18 pp., arXiv: 2003.06177
187. M. V. Volkov, “Synchronizing automata and the Černý conjecture”, Language and automata theory and applications, Lecture Notes in Comput. Sci., 5196, Springer, Berlin, 2008, 11–27  crossref  mathscinet  zmath
188. M. V. Volkov, “Synchronizing automata preserving a chain of partial orders”, Theoret. Comput. Sci., 410:37 (2009), 3513–3519  crossref  mathscinet  zmath
189. M. V. Volkov, “Slowly synchronizing automata with idempotent letters of low rank”, J. Autom. Lang. Comb., 24:2-4 (2019), 375–386  crossref  mathscinet  zmath
190. V. Vorel, Synchronization and discontinuous input processing in transition systems, Doctoral thesis, Charles Univ., Prague, 2018, 137 pp., \par https://dspace.cuni.cz/handle/20.500.11956/104303
191. V. Vorel, A. Roman, “Parameterized complexity of synchronization and road coloring”, Discrete Math. Theor. Comput. Sci., 17:1 (2015), 283–305  crossref  mathscinet  zmath
192. H. Wielandt, “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642–648  crossref  mathscinet  zmath
193. D. Zuckerman, “Linear degree extractors and the inapproximability of max clique and chromatic number”, Theory Comput., 3 (2007), 6, 103–128  crossref  mathscinet  zmath

Образец цитирования: М. В. Волков, “Синхронизация конечных автоматов”, УМН, 77:5(467) (2022), 53–130; Russian Math. Surveys, 77:5 (2022), 819–891
Цитирование в формате AMSBIB
\RBibitem{Vol22}
\by М.~В.~Волков
\paper Синхронизация конечных автоматов
\jour УМН
\yr 2022
\vol 77
\issue 5(467)
\pages 53--130
\mathnet{http://mi.mathnet.ru/rm10005}
\crossref{https://doi.org/10.4213/rm10005}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4582587}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022RuMaS..77..819V}
\transl
\jour Russian Math. Surveys
\yr 2022
\vol 77
\issue 5
\pages 819--891
\crossref{https://doi.org/10.4213/rm10005e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000992306600002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85165308000}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/rm10005
  • https://doi.org/10.4213/rm10005
  • https://www.mathnet.ru/rus/rm/v77/i5/p53
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
    Статистика просмотров:
    Страница аннотации:798
    PDF русской версии:89
    PDF английской версии:292
    HTML русской версии:480
    HTML английской версии:279
    Список литературы:99
    Первая страница:40
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024