Laboratory of Mathematical Logic at PDMI

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

Докладчик: Б. Ф. Мельников (Ульяновский гос.университет).

ПРОСТОЕ РЕШЕНИЕ ПРОБЛЕМЫ ЗВЕЗДНОЙ ВЫСОТЫ (Часть I)
Проблема звездной высоты регулярного языка была поставлена в самом начале 1960-х годов и очень долгое время оставалась нерешенной. Кратко сама проблема может быть сформулирована следующим образом: определяем звездную высоту (ЗВ) регулярного выражения (РВ) как максимальное вложение в нем операции "звезда"; известно, что для каждого регулярного языка (РЯ) существует бесконечно много РВ, определяющих этот язык; существует ли алгоритм, определяющий, какое именно из этих РВ имеет минимальную ЗВ? В 1987-м году вышла пока единственная публикация с довольно сложным алгоритмом, решающим данную проблему (K.Hashiguchi).
Автор данных тезисов предлагает значительно более простое решение, базирующееся на построении специальных недетерминированных конечных автоматов (КА). Данное решение является продолжением серии работ автора, связанных с исследованием РЯ с помощью т.н. функций разметки состояний КА; в тех работах, среди прочих, были решены задачи минимизации КА по другим критериям - вершинной и дуговой.
Вторая часть доклада состоится на заседании семинара лаборатории математической логики ПОМИ в понедельник, 18 марта в 14:00, к.203.