Пятница, 5 апреля, комната 106. Начало в 18:00.
Докладчик: Ю. Лифшиц.
СВЯЗЬ КОНЕЧНЫХ АВТОМАТОВ С РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ ЗАДАЧА ОБ УНИВЕРСАЛЬНОМ ГРАФЕ
Эта задача возникла в теории конечных автоматов. Известно, что для языка каждого регулярного выражения существует конечный автомат, который этот язык распознает. При попытке дать нижнюю оценку количества переходов в этом автомате Hagenah и Muscholl сформулировали следущий результат:
Количество переходов в конечном недетерминированном автомате без пустых переходов, который распознает регулярный язык из
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
букв -- не меньше, чем количество ребер в Универсальном графе (УГ).
В той же статье получена и верхняя оценка:
Для любого регулярного выражения, построенного за
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
шагов, можно построить недетерминированный конечный автомат без пустых переходов, который будет распознавать язык этого выражения и содержать не более чем
![$ С n log^2 n $](../../../sites/default/files/tex/4bcb47586866e3ab94ff491d566e81434f47d1b8/index.png)
переходов.
Таким образом, цель настоящей работы -- получить нижнюю оценку на количество ребер в УГ. Оценка, полученная в работе Hagenah и Muscholl --
![$ c n log n $](../../../sites/default/files/tex/c0ac49d3acd35198863e955532870e8f87fdd6fe/index.png)
. Результат настоящей работы -- нижняя оценка
![$ c_1 n log^2 n/log log n $](../../../sites/default/files/tex/f77fa2f6c7f488170f1af50815ca7e0a49fcbad9/index.png)
. Основная идея доказательства -- переход от ориентированного графа к стрелочным структурам. Однако, по мнению автора, таким путем невозможно получить оценку
![$ c_2 n log^2 n $](../../../sites/default/files/tex/78fae116035281b87752b3640f23c8fab932e8e2/index.png)
.