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

Ближайший семинар «Категориальные грамматики» состоится 17 апреля (17.04.2025).

Начало: 18:30. Аудитория: 1605, кафедра математической логики и теории алгоритмов (возможно, аудитория изменится).

Докладчик: Т.Г. Пшеницын
Тема: Грамматики слияния, сохраняющие связность

Рассматриваются ориентированные гиперграфы, гиперребра которых помечены символами некоторого алфавита. У каждого символа есть комплементарный ему. На гиперграфах определена операция слияния: два гиперребра с комплементарными метками "склеиваются" и удаляются. В грамматике слияния разрешено брать неограниченное число изоморфных копий гиперграфов из фиксированного конечного набора и применять к ним слияния; грамматика порождает компоненты связности получающихся таким образом гиперграфов. Мотивация изучения такого формализма связана с моделированием взаимодействия молекул ДНК; можно смотреть на грамматики слияния и как на своеобразное логическое исчисление с "правилом сечения" (выводимые объекты такого исчисления — связные гиперграфы).

При исследовании алгоритмических и теоретико-языковых свойств грамматик слияния возникли трудности, связанные с тем, что слияние может приводить к нарушению связности: при слиянии между двумя связными гиперграфами или внутри одного связного гиперграфа может получаться несвязный гиперграф. Чтобы исключить нарушения связности, в литературе было введено понятие грамматик слияния, сохраняющих связность. Оказалось, что для них многие задачи решаются проще, чем для грамматик слияния в целом (проще — и в смысле алгоритмической сложности, и в смысле простоты доказательств). Так, Aaron Lye в 2021 году доказал, что задача непустоты для грамматик слияния, сохраняющих связность, разрешима и является NP-полной; также он получил аналогичный результат в отношении задачи принадлежности для существенных грамматик слияния, сохраняющих связность. Докладчиком также был доказан аналог теоремы Париха для грамматик слияния, сохраняющих связность (верно ли это для всех грамматик слияния, неизвестно).

В докладе будет описано свойство сохранения связности и будет дан обзор упомянутых выше результатов. Основной акцент будет сделан на сложности самого свойства сохранения связности: будет доказано, что задача проверки, сохраняет ли грамматика слияния связность, разрешима, принадлежит классу coNEXPTIME и при этом PSPACE-трудна. Доказательства иллюстрируют типичные для данной области методы.

➰ ВК