Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Оценки длины слов, имеющих заданный ранг относительно ДКА (Сергей Вельдер, кафедра компьютерных технологий СПбГУ ИТМО)
Computer Science семинар

Что: Лекция
Когда: Воскресенье, 15 мая 2011, 15:35–17:10
Где: ПОМИ РАН
Слайды: csseminar_lecture_150511.pdf

Описание

Гипотеза Ж.-Э. Пэна и гипотеза о рангах дают верхние оценки на длину слов, имеющих ранг k относительно детерминировнного конечного автомата (ДКА) из n состояний. Эти верхние оценки можно выразить функцией от (n-k), не зависящей от самих величин n, k и от автомата. Точная верхняя оценка является функцией, перечислимой снизу путём перебора всех ДКА. Это означает, что если для каких-то n и k верхняя оценка не выполняется, то данный факт можно подтвердить предъявлением ДКА, который играет роль автоматически проверяемого сертификата. В докладе будут рассмотрены комбинаторные структуры, которые можно использовать в качестве автоматически проверяемых сертификатов для ситуации, когда верхняя оценка выполняется. Они позволяют установить перечислимость сверху точной верхней оценки на длину слов и, как следствие, машинно доказывать такие оценки для всех ДКА, а также определить время, достаточное для вычисления этих оценок.