Алгебраические методы изучения звёздной высоты регулярных языков

Звёздная высота регулярного языка — минимальное число вложенных итераций Клини ("звёздочек" Клини), необходимое для описания этого языка регулярным выражением.

В докладе я сконцентрируюсь на "extended star height" — варианте, допускающем использование в регулярном выражении операций дополнения, объединения, итерации Клини и конкатенации. Основным имеющимся инструментом для изучения свойств регулярных языков при таком определении являются синтаксические моноиды.

В докладе будут рассмотрены основные взаимосвязи между звёздной высотой регулярных языков и структурой их синтаксических моноидов. Кроме того, будут упомянуты перспективы использования алгебраических свойств регулярных языков в зависимости от того, существуют ли языки звёздной высоты больше 1.