📢
Репост из группы
Кафедра математической логики МГУ:
#матлог #учёба #спецсеминар
На онлайн-заседании объединенного семинара кафедры математической логики и теории алгоритмов МГУ
"Модальная и алгебраическая логика" и "Логические методы в информатике"
в ближайший четверг 25 февраля, начало в 18:30, состоится продолжение доклада
Т. Г. Пшеницын
Гиперграфовые грамматики Ламбека
Данный доклад (который, вероятно, займет 2 лекции) продолжает тематику докладов по обобщению исчисления Ламбека на гиперграфы, однако посвящен принципиально новому разделу — грамматикам. Гиперграфовое исчисление Ламбека возникло из желания совместить принципы обычного исчисления Ламбека с принципами грамматик замещения гиперребер. В частности, по аналогии с обычными грамматиками Ламбека, можно определить гиперграфовые грамматики Ламбека (ГГЛ). Эти грамматики представляют собой альтернативный грамматикам замещения гиперребер формализм для порождения гиперграфовых языков. Будет показано, что ГГЛ, с незначительными исключениями, порождают все контекстно-свободные гиперграфовые языки (что является прямым обобщением теоремы Гайфмана). Также будет доказана NP-полнота проверки принадлежности гиперграфа языку, задаваемому данной ГГЛ.
Ключевой вопрос, на который будет дан ответ в данном докладе — выполняется ли для ГГЛ теорема Пентуса: верно ли, что всякий язык, порождаемый ГГЛ, является контекстно-свободным? Несколько неожиданный ответ — нет. Так, данные грамматики могут порождать язык всех графов без изолированных вершин, язык всех двудольных графов без изолированных вершин. Кульминационный результат заключается в том, что ГГЛ порождают конечные пересечения контекстно-свободных гиперграфовых языков. Из этого будет следовать в том числе, что ГГЛ могут порождать строковые языки, которые не порождаются грамматиками замещения гиперребер, а также то, что для них не выполняется теорема Парика.
Видеозаписи предыдущих докладов:
https://www.youtube.com/playlist?list=PLEBNQnjHceeVxr2o766qqr993dyaKWRCXВеб-страница с аннотациями и слайдами:
http://lpcs.math.msu.su/rus/ml.htmДля получения ссылки на конференцию Zoom пишите на почту aleksandr.zapryagaev@yandex.ru.
Убедительно просим всех подключающихся указывать в Zoom свои настоящие имя и фамилию!