Пятница, 16 октября, комната 106. Начало в 18:00.
Докладчик: А. С. Охотин (университет Турку, Финляндия).
Тема: Конечные автоматы над однобуквенным алфавитом.
Abstract
Известно несколько разновидностей конечных автоматов --- детерминированные и недетерминированные односторонние и двухсторонние --- однако все они задают одно и то же семейство "регулярных языков". В то же время, число состояний, необходимое для распознавания того или иного языка, существенно отличается для разных моделей. Доклад посвящён автоматам над однобуквенным алфавитом и оценкам роста числа состояний при переводе таких автоматов к равносильным детерминированным односторонним автоматам (1DFA).
Из работ Любича (1964) и Хробака (1986) известно, что недетерминированные конечные автоматы (1NFA) с n состояниями требуют 1DFA с
![$ g(n)+O(n2)=e^{\sqrt{n \ln n}(1+o(1))} $](../../../sites/default/files/tex/f421ae589f218e776c5b03ba0f55cc603339b720/index.png)
состояниями, где
![$ g(n) $](../../../sites/default/files/tex/cd06a2db5c62c64f050d7121adf94fdd4dc32437/index.png)
--- наибольший порядок перестановки из n элементов. В докладе будут представлены два новых результата такого рода. Во-первых, однозначный недетерминированный конечный автомат (1UFA) с n состояниями требует 1DFA с
![$ e^{\Theta(\sqrt[3]{n \ln2 n})} $](../../../sites/default/files/tex/bea07986a7ef07df4617ae9d66899c542ef5ff1d/index.png)
состояниями. Во-вторых, двусторонний детерминированный конечный автомат (2DFA) требует ровно
![$ \max_l g(n-l)+l+1 $](../../../sites/default/files/tex/d1d1d7a244eb9ddcb5c364f4c0a8a9f37b924fa4/index.png)
состояний 1DFA.
Результат по двухсторонним автоматам получен совместно с Михалом Кунцем из Брненского университета (Чехия).