|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Минимальные разложения регулярных языков на языки без объединениятезисы доклада
- Авторы: Афонин С.А., Голомазов Д.Д.
- Сборник: Ломоносовские чтения. Тезисы докладов научной конференции. Секция механики. Апрель 2009
- Тезисы
- Год издания: 2009
- Место издания: Издательство Московского университета
- Первая страница: 22
- Последняя страница: 22
- Аннотация: Настоящий доклад посвящен вопросам, связанным с так называемыми "языками без объединения" (union-free languages), а также задаче построения минимального (по количеству элементов) разложения произвольного регулярного языка в сумму языков без объединения. В первой части доклада формулируются определения необходимых понятий, в том числе введенного авторами термина "ширина объединения регулярного языка", которое является аналогом понятия "звездная высота" и означает количество элементов в минимальном разложении регулярного языка. Во второй части доклада приводится формальная постановка задачи, решаемой в работе, а именно, задачи разработки алгоритма построения минимального разложения произвольного регулярного языка в сумму языков без объединения. Авторами рассматриваются "наивные" пути решения данной задачи и приводятся контрпримеры, показывающие, что эти методы не дают искомого результата. В третьей части доклада приводится описание разработанного авторами алгоритма построения минимального разложения произвольного регулярного языка в сумму языков без объединения. Описывается план доказательства теоремы, которая подтверждает его корректность и тот факт, что при использовании алгоритма действительно получается минимальное разложение. В качестве дополнительного результата, полученного авторами, приводится новый алгоритм проверки того факта, является ли произвольный регулярный язык языком без объединения. В четвертой части доклада отмечаются возможные сферы применения результатов, полученных в работе. Приводится оценка сложности разработанного авторами алгоритма построения минимального разложения, а также один из возможных подходов к разработке более эффективных алгоритмов, решающих рассматриваемую задачу, а именно, метод "отрезания звезд".