On-The-Fly Static Analysis via Dynamic Bidirected Dyck Reachability
summary
Provides a dynamic algorithm for bidirected Dyck reachability with worst-case O(n·α(n)) per update (beating the prior O(n2) worst case), implements it, and evaluates it against the optimal offline algorithm and a fully dynamic Datalog solver. Handles both edge insertions and deletions by maintaining a primary Dyck SCC decomposition and restarting local merges instead of full recomputation, achieves practical update times that are almost always imperceptible and reports empirical ~1000X speedup over alternatives on tens- to hundreds-of-thousands-node program graphs.
AI-written summary · about