Гиперграфовые грамматики Ламбека, часть 1. Тихон Пшеницын (18.02.2021)

Данный (и следующий) доклад продолжает тематику докладов по обобщению исчисления Ламбека на гиперграфы, однако посвящен принципиально новому разделу — грамматикам.

Гиперграфовое исчисление Ламбека возникло из желания совместить принципы обычного исчисления Ламбека с принципами грамматик замещения гиперребер. В частности, по аналогии с обычными грамматиками Ламбека, можно определить гиперграфовые грамматики Ламбека (ГГЛ). Эти грамматики представляют собой альтернативный грамматикам замещения гиперребер формализм для порождения гиперграфовых языков. Будет показано, что ГГЛ, с незначительными исключениями, порождают все контекстно-свободные гиперграфовые языки (что является прямым обобщением теоремы Гайфмана). Также будет доказана NP-полнота проверки принадлежности гиперграфа языку, задаваемому данной ГГЛ.

Ключевой вопрос, на который будет дан ответ в данном докладе — выполняется ли для ГГЛ теорема Пентуса: верно ли, что всякий язык, порождаемый ГГЛ, является контекстно-свободным? Несколько неожиданный ответ — нет. Так, данные грамматики могут порождать язык всех графов без изолированных вершин, язык всех двудольных графов без изолированных вершин. Кульминационный результат заключается в том, что ГГЛ порождают конечные пересечения контекстно-свободных гиперграфовых языков. Из этого будет следовать в том числе, что ГГЛ могут порождать строковые языки, которые не порождаются грамматиками замещения гиперребер, а также то, что для них не выполняется теорема Парика.

Докладчик: Пшеницын Тихон Григорьевич, 4 курс (науч. рук. М. Р. Пентус)

Предыдущие доклады на данную тему:

Позвольте представить: Грамматики замещения гиперрёбер

Гиперграфовое исчисление Ламбека:
______________________________

Совместные заседания научных семинаров
«Логические проблемы информатики»
(руководители: проф. С.Н.Артёмов, акад. РАН Л.Д.Беклемишев,
доц. В.Н.Крупский, проф. М.Р.Пентус, доц. Т.Л.Яворская) и
«Модальная и алгебраическая логика»
(руководители: проф. М.Р.Пентус,
проф. В.Б.Шехтман, к.ф.-м.н. И.Б.Шапировский)
проходят по четвергам в 17 : 45.

Веб-страница (слайды, ссылка zoom):