Исследовательская группа

Лаборатория языковых инструментов

Публикации

  • R. Azimov and S. Grigorev

    Path querying with conjunctive grammars is known to be undecidable. There is an algorithm for path querying with linear conjunctive grammars which provides an over-approximation of the result, but there is no algorithm for arbitrary conjunctive grammars. We propose the first algorithm for path querying with arbitrary conjunctive grammars. The proposed algorithm is matrix-based and allows us to efficiently apply GPGPU computing techniques and other optimizations for matrix operations.

    Programming and Computer Software,
  • Egor Namakonov, Anton Podkopaev
    Proceedings of ISP RAS,
  • Evgenii Moiseenko, Anton Podkopaev, Ori Lahav, Orestis Melkonian, Viktor Vafeiadis
    arXiv,
  • Semyon Grigorev and Polina Lunina
    BMC Bioinformatics,
  • D. Mordvinov, G. Fedyukovich
    Proceedings of 19th International Conference on Formal Methods in Computer-Aided Design, FMCAD 2019,
  • A. Misonizhnik, D. Mordvinov
    33rd European Conference on Object-Oriented Programming (ECOOP 2019),
  • Sergey Bozhko, Leyla Khatbullina, Semyon Grigorev

    The Bar-Hillel theorem states that context-free languages are closed under intersection with a regular set. This theorem has a constructive proof and thus provides a formal justification of correctness of the algorithms for applications mentioned above. Mechanization of the Bar-Hillel theorem, therefore, is both a fundamental result of formal language theory and a basis for the certified implementation of the algorithms for applications. In this work, we present the mechanized proof of the Bar-Hillel theorem in Coq.

    Logic, Language, Information, and Computation,
  • Nikita Mishin, Iaroslav Sokolov, Egor Spirin, Vladimir Kutuev, Egor Nemchinov, Sergey Gorbatyuk, and Semyon Grigorev

    Recently proposed matrix multiplication based algorithm for context-free path querying (CFPQ) offloads the most performance-critical parts onto boolean matrices multiplication. Thus, it is possible to achieve high performance of CFPQ by means of modern parallel hardware and software. In this paper, we provide results of empirical performance comparison of different implementations of this algorithm on both real-world data and synthetic data for the worst cases.

    Proceedings of the 2nd Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA),
  • Semyon Grigorev and Polina Lunina

    We propose a way to combine formal grammars and artificial neural networks for biological sequences processing. Formal grammars encode the secondary structure of the sequence and neural networks deal with mutations and noise. In contrast to the classical way, when probabilistic grammars are used for secondary structure modeling, we propose to use arbitrary (not probabilistic) grammars which simplifies grammar creation. Instead of modeling the structure of the whole sequence, we create a grammar which only describes features of the secondary structure. Then we use matrix-based parsing to extract features: the fact that some substring can be derived from some nonterminal is a feature. After that, we use a dense neural network to process features.

    Proceedings of the 12th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS,
  • Shemetova E.N., Grigorev S.V.

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

    Proceedings of the Institute for System Programming,

Сортировка: