Path querying on acyclic graphs using Boolean grammars

DOI10.1134/S036176882008006XzbMath1477.68094OpenAlexW2981496360MaRDI QIDQ2027852

E. N. Shemetova, S. V. Grigor'ev

Publication date: 28 May 2021

Published in: Programming and Computer Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s036176882008006x

Mathematics Subject Classification ID

Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Uses Software

• SPARQL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parsing by matrix multiplication generalized to Boolean grammars
• General context-free recognition in less than cubic time
• Boolean grammars
• Regular queries on graph databases
• An Efficient Algorithm for Solving the Dyck-CFL Reachability Problem on Trees
• Finding Regular Simple Paths in Graph Databases
• Context-sensitive data-dependence analysis via linear conjunctive language reachability
• Multiplying matrices faster than coppersmith-winograd
• Properties of deterministic top-down grammars

This page was built for publication: Path querying on acyclic graphs using Boolean grammars