О достижимости с ограничениями в терминах формальных языков

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

• Поиск путей с регулярными ограничениями, Regular Path Querying, RPQ.
• Поиск путей с контекстно-свободными ограничениями, Context-Free Path Querying, CFPQ.
• Достижимость с контекстно-свободными ограничениями, Context-Free Language Reachability, CFL-r.

Указанные выше англоязычные термины полезны для того, чтобы найти больше информации по теме.

Так как текст во многом основан на опыте исследовательской группы, работающей в данной области, то он неизбежно будет меняться, вместе с изменением понимания предмета у авторов.

Полезен данный текст может быть, как кажется, в нескольких перечисленных ниже случаях.

• Если хочется получить представление о задаче поиска путей с ограничениями в терминах формальных языков и об основных подходах к её решению.
• Если вы занимаетесь изучением теории формальных языков или алгоритмов синтаксического анализа и хотите увидеть больше применений этих областей на практике.
• Если вы преподаёте теорию формальных языков и хотите рассказать о её приложениях, отличающихся от анализа естественных языков или языков программирования.

Скачать pdf

• Текущую версию можно найти в артефактах сборки.
• Официальные "издания" можно найти в релизах.

Собрать из исходников

Если вы решили что-то изменить в тексте или просто собрать pdf из исходников, то необходимо проделать следующие шаги.

• Устанвить TeX Live или аналогичный дистрибутив.
• Сделать клон репозитория.
• Зайти в папку tex.
• Выполнить команду

make

Задать вопрос

• Задать вопрос, высказать пожелания или предложения можно в разделе для дискуссий.
• Сообщить о неточностях, ошибках в тексте, технических проблемах с компиляцией pdf из исходников можно заведя issue.
• Внести свой вклад в развитие проекта можно сдлеав fork и открыв pull request.

Лицензия

Данный текст опубликован под лицензией Creative Commons Attribution Share Alike 4.0 International.