Path querying on acyclic graphs using Boolean grammars
| Autor: | Semyon V. Grigorev, Ekaterina N. Shemetova |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Theoretical computer science
булевы грамматики Computer science Relational database Static program analysis 0102 computer and information sciences 02 engineering and technology computer.software_genre 01 natural sciences lcsh:QA75.5-76.95 Rule-based machine translation 0202 electrical engineering electronic engineering information engineering Logical matrix Computer Science::Databases General Environmental Science Discrete mathematics ациклический граф Graph database String (computer science) произведение матриц 020207 software engineering Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Directed graph булевы матрицы поиск путей с ограничениями Directed acyclic graph Undecidable problem матричные операции Formal grammar 010201 computation theory & mathematics Terminal and nonterminal symbols Path (graph theory) General Earth and Planetary Sciences lcsh:Electronic computers. Computer science computer Software |
| Zdroj: | Труды Института системного программирования РАН, Vol 31, Iss 4, Pp 211-226 (2019) |
| ISSN: | 2220-6426 2079-8156 |
| Popis: | Graph data models are widely employed in different areas of computer science, e.g., graph databases, bioinformatics, social network analysis, and static code analysis. Querying for specific paths is one of the main problems solved in graph data analysis. Path queries are usually performed by means of a formal grammar that describes admissible edge labeling of the paths. A path query is said to be calculated using relational query semantics if it is evaluated to a triple (A, $${{{v}}_{1}}$$ , $${{{v}}_{2}}$$ ) such that there is a path from $${{{v}}_{1}}$$ to $${{{v}}_{2}}$$ and the concatenation of the edge labels along this path forms a string derivable from the nonterminal A. With the regular and context-free languages having limited expressive power, we focus on more expressive languages, namely, Boolean languages that use Boolean grammars to describe path labeling. Even though path querying using relational query semantics and Boolean grammars is known to be undecidable, in this paper, we propose a path querying algorithm on acyclic directed graphs that uses relational query semantics and Boolean grammars for approximate solution of the path querying problem. To achieve better performance as compared to the naive algorithm, the classes of graphs considered in this paper are limited to acyclic graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|