#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/).

Время: 9 октября (четверг), 16:00
Место: МИАН, ауд. 530 + Контур.Толк

Ю.Д. Теляковская (НИУ ВШЭ)

О свойствах звёздной высоты регулярных языков

Аннотация:
Звёздная высота регулярного выражения — минимальное число вложенных операций звезды Клини, необходимое для записи этого языка регулярным выражением. Известно, что для любого натурального числа существует регулярный язык такой звёздной высоты. Однако при добавлении к используемым для записи регулярных выражений операций (конкатенации, объединению и звезде Клини) дополнения ситуация меняется: неизвестно ни одного регулярного языка, при записи которого выражением с дополнением звёздная высота окажется больше 1.
В докладе я планирую рассмотреть некоторые примеры влияния на звёздную высоту языков добавления к алфавиту регулярных выражений различных операций, а так же связь звёздной высоты языка со свойствами конечных автоматов, задающих данный язык.

Если планируете посетить заседание (очно или онлайн через Контур.Толк), пожалуйста, зарегистрируйтесь по ссылке в верхней части страницы семинара:
https://www.mathnet.ru/conf2533

➰ ВК