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

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

Поиск путей с регулярными ограничениями, 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.