О некоторых частных случаях задачи поиска путей с контекстно-свободными ограничениями

Задача поиска путей с контекстно-свободными ограничениями является одной из важных задач в работе с графовыми моделями данных. Создано множество алгоритмов для её решения, но все они недостаточно эффективны для применения на практике, так что разрабатываются частные решения, более оптимальные, чем общие. Однако существующие частные решения слишком разнородны и не могут быть переиспользованы для построения новых алгоритмов. В данной работе был предложен общий подход к созданию эффективных частных решений, заключающийся в модификациях алгоритма, основанного на идее пересечения языков и поддержке инкрементального транзитивного замыкания. Одной из таких модификаций является работа с неориентированными графами вместо ориентированных. Полученный с её помощью алгоритм применим для решения задачи поиска путей с контекстно-свободными ограничениями на двунаправленных графах и языке Дика. Вторая модификация заключается в пересчёте транзитивного замыкания после каждой итерации добавления рёбер, вместо поддержки обновления отношения достижимости при одиночном добавлении. Такое решение применимо при малом числе итераций пересчёта транзитивного замыкания. Для языка Дика на одном типе скобок была сконструирована специальная грамматика, дающее полилогарифмическое число итераций и, следовательно, субкубический алгоритм. Также идея пересечения языков была использована для ускорения решения другой задачи, а именно, поиска путей с ограничениями, заданными смешанным языком Дика. Ключевые слова: задача достижимости, графовые алгоритмы, формальные языки, транзитивное замыкание, частные случаи