С: 16.09.2026 18:30 по: 16.09.2026 20:00

В среду, 16 сентября, в 18:30 в аудитории 1213 на заседании кафедрального семинара
"Теория автоматов" состоится доклад В.А. Бирюковой "О предполных классах в
классе линейных автоматов относительно операторов композиции и
аппроксимационного замыкания".

Заседание состоится в смешанном формате. Очная часть пройдет в аудитории 1213,
дистанционная - в zoom-конференции

https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09

Meeting ID: 886 6514 1982
Passcode: 965515

Анонс доклада:
В докладе рассматривается класс линейных автоматов \(L_2\) над полем \(E_2\). Этот
класс примечателен тем, что в нём проблема полноты алгоритмически разрешима
относительно двух операторов - K- и A-замыкания, и для обоих случаев
построены критериальные системы. Однако до настоящей работы оставались
открытыми вопросы о K-конечнопорожденности этих предполных классов, пять из
которых составляют первый уровень решётки A-замкнутых классов, а также о
структуре второго уровня этой решётки.

Для всех K-предполных классов решена задача K-конечнопорожденности:
установлен критерий, построены конечные базисы для классов A-критериальной
системы и доказана неконечнопорожденность всех остальных предполных классов.
Проведена полная классификация A-замкнутых классов второго уровня решётки, и
для всех найденных классов, за исключением одного, предъявлены конечные базисы.
Для этого единственного класса доказано, что для него не существует конечной
порождающей системы; более того, показано, что он является наибольшим по
включению A-замкнутым классом, не являющимся K-конечнопорожденным.

Таким образом, в докладе получены следующие результаты: решена задача
K-конечнопорожденности для всех K-предполных классов, а также проведена
полная классификация классов второго уровня решётки A-замкнутых классов, и
для них решена задача K-конечнопорожденности.