Fast point-to-point Dyck constrained shortest paths on a DAG (Extended abstract)
Phillip G. Bradford, Venkatesh Choppella · 2016
Many aspects of program analysis are related to CFL (context-free language) constrained path problems on graphs. A path is constrained by requiring its list of edge labels to form a string that is a member of the associated CFL. Constrained shortest path problems give O(n3/ log n)-bottlenecks for program analysis, where n is the number of nodes. Labeled path problems also have many other applications. Assume two terminals (parenthesis) in a Dyck CFL. Given any two vertices s and t and the output of Nykanen and Ukkonen's exact integer path length algorithm. then this paper finds a minimal-cost point-to-point Dyck path cost in such edge-labeled digraphs in O(n2 log n) additional operations. This paper is on the DAG (directed acyclic graph) case. Our result depends on a special case of the exact integer path length problem of Nykanen and Ukkonen that costs O(n3). A new algorithm is introduced that joins special edges output by Nykanen and Ukkonen's algorithm. Nykanen and Ukkonen's algorithm along with our basic algorithm gives a minimal-cost point-to-point Dyck shortest path cost between two nodes.