Т. Г. Пшеницын, “О сложности распознавания грамматик слияния, сохраняющих связность”, Сириус. Матем. журнал, 1:4 (2025), 80–94.

Грамматики слияния — вид графовых грамматик — ввели Х.-Й. Креовски, С. Кушке, А. Лай в 2017 г. Эти грамматики позволяют порождать гиперграфы с помощью операции слияния — преобразования, состоящего из склеивания гиперребер с комплементарными метками и последующего удаления этих гиперребер. В 2021 г. А. Лай определил свойство сохранения связности: грамматика слияния сохраняет связность, если результат слияния внутри одной компоненты связности либо между двумя компонентами связности любого гиперграфа, порождаемого этой грамматикой — связный гиперграф. Наличие этого свойства облегчает анализ ряда алгоритмических и теоретико-языковых задач, касающихся грамматик слияния.

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

Работа поддержана грантом Фонда развития теоретической физики и математики «БАЗИС», грант 24-7-5-15-1.

T. G. Pshenitsyn, “The complexity of recognizing connection-preserving fusion grammars,” J. Math. Sci. (New York), 294:6 (2025), 915−931.
DOI: 10.1007/s10958-025-08172-7