Abstract
The problem of matching one or more graphs or subgraphs with a non-deterministic finite automaton (NFA) is of importance in various domains of computer science. An example is regular-expression matching, which can be formulated as a graph-matching problem. Current techniques of matching multiples graphs or subgraphs against NFAs have relatively high computational complexity. This disclosure presents matching techniques with complexity that is linear in the size of the graph. A single, larger, graph is constructed from the set of graphs to be matched. The larger graph is considered as an NFA. A single-NFA to single-NFA matching procedure of linear space and time complexity is employed to match the larger graph against the NFA. Overlaps between the set of graphs or subgraphs are leveraged to produce gains in computational efficiency.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Boulgakov, Alexandre, "Efficient multi-graph or rooted subgraph matching via merging", Technical Disclosure Commons, (June 18, 2018)
https://www.tdcommons.org/dpubs_series/1252