A data structure for arc insertion and regular path finding
Adam L. Buchsbaum, Paris Christos Kanellakis, Jeffrey Scott Vitter · Symposium on Discrete Algorithms · 1990
If $G$ is a directed graph with labeled edges and $L$ is a fixed regular language, the {\em regular path problem}, given two nodes, $u$ and $v$, in $G$, is to find a path between $u$ and $v$ such that the labels on the arcs along that path form a string which is a member of $L$. We consider a dynamic version of this problem, adding arcs to and performing regular path queries on $G$ over $L$, and present a data structure that solves both problems in average time per operation linear in the number of nodes of the graph for any fixed regular language.