Графовые грамматики

Русский язык, язык C++ и язык математики — все называются языками. Это осмысленно с точки зрения теории формальных языков, которая называет языком любое множество строк. Ясно, что интерес представляет задача алгоритмически эффективного описания языков, упомянутых выше, или, иными словами, задача эффективной проверки корректности строки (то есть, например, задачи проверки, является ли строка грамматически корректным предложением русского языка или является ли строка корректным текстом программы на языке C++). Способы решения этих задач изучаются теорией формальных грамматик. Самым известным видом таких грамматик являются контекстно-свободные грамматики, введённые Ноамом Хомским; они активно изучаются последние 65 лет. Мы расскажем про обобщения формальных грамматик и, в частности, контекстно-свободных грамматик на графы — графовые грамматики. В отличие от формальных грамматик для строк, в случае графовых грамматик есть несколько конкурирующих парадигм, основанных на фундаментально различных механизмах преобразования графов. Мы обозрим два таких механизма: замещение вершин и замещение рёбер. Также слушателям будет кратко представлена алгебраическая теория преобразований графов, которая основывается на теоретико- категорных понятиях. Наконец, будут рассмотрены приложения графовых грамматик в различных областях.