Abstract
The problem of matching a graph 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 graphs against NFAs have relatively high computational complexity. This disclosure presents matching techniques with complexity that is linear in the size of the graph. The graph to be matched against the NFA is itself considered as an NFA. A synchronized product of the two NFAs is defined, and the matching problem is shown equivalent to a reachability problem solvable in linear (time and space) complexity.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
Boulgakov, Alexandre, "Matching a graph with a non-deterministic finite automaton", Technical Disclosure Commons, (June 14, 2018)
https://www.tdcommons.org/dpubs_series/1246