Екатерина Шеметова

Биография

Екатерина получила степень магистра в области разработки программного обеспечения в Университете ИТМО. В настоящее время является аспирантом по направлению "Информатика и вычислительная техника" в Санкт-Петербургском Академическом университете.

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

Проекты

Публикации

  • Shemetova E.N., Grigorev S.V.
    Path querying on acyclic graphs using Boolean grammars

    Одной из основных задач, связанных с графовыми моделями, является поиск специфичных путей в графе. Естественным способом задать ограничения на пути являются формальные грамматики над метками рёбер графа, при этом запрос к графу может быть представлен в виде множества всех троек (A,v1,v2), для которых существует путь в графе от вершины v1 до вершины v2 такой, что метки на ребрах этого пути образуют строку, выводимую из нетерминала A в данной грамматике. В данной работе исследуются Булевы грамматики. Известно, что задача выполнения запросов к графу с использованием булевых грамматик является неразрешимой. В данной работе предложен приближённый алгоритм поиска путей в ориентированных графах без циклов с ограничениями, заданными с помощью булевых грамматик. Благодаря ограничению на тип анализируемых графов, предложенный алгоритм является более асимптотически оптимальным, чем наивный итерационный алгоритм.

    Proceedings of the Institute for System Programming, Январь 2019