Home

Пятница, 16 октября, 18:00, к. 106

Пятница, 16 октября, комната 106. Начало в 18:00.

Докладчик: А. С. Охотин (университет Турку, Финляндия).

Тема: Конечные автоматы над однобуквенным алфавитом.

Abstract

Известно несколько разновидностей конечных автоматов --- детерминированные и недетерминированные односторонние и двухсторонние --- однако все они задают одно и то же семейство "регулярных языков". В то же время, число состояний, необходимое для распознавания того или иного языка, существенно отличается для разных моделей. Доклад посвящён автоматам над однобуквенным алфавитом и оценкам роста числа состояний при переводе таких автоматов к равносильным детерминированным односторонним автоматам (1DFA).

Из работ Любича (1964) и Хробака (1986) известно, что недетерминированные конечные автоматы (1NFA) с n состояниями требуют 1DFA с $ g(n)+O(n2)=e^{\sqrt{n \ln n}(1+o(1))} $ состояниями, где $ g(n) $ --- наибольший порядок перестановки из n элементов. В докладе будут представлены два новых результата такого рода. Во-первых, однозначный недетерминированный конечный автомат (1UFA) с n состояниями требует 1DFA с $ e^{\Theta(\sqrt[3]{n \ln2 n})} $ состояниями. Во-вторых, двусторонний детерминированный конечный автомат (2DFA) требует ровно $ \max_l g(n-l)+l+1 $ состояний 1DFA.

Результат по двухсторонним автоматам получен совместно с Михалом Кунцем из Брненского университета (Чехия).