{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T13:33:28Z","timestamp":1790948008181,"version":"4.1.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1917924, 2114627"],"award-info":[{"award-number":["1917924, 2114627"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["N66001-21-C-4024"],"award-info":[{"award-number":["N66001-21-C-4024"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,1,16]]},"abstract":"<jats:p>\n            Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls\/returns and field writes\/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on\n            <jats:italic>bidirected graphs<\/jats:italic>\n            where each edge\n            <jats:italic>u<\/jats:italic>\n            \u2192\n            <jats:sup>\n              (\n              <jats:sub>\n                <jats:italic>i<\/jats:italic>\n              <\/jats:sub>\n            <\/jats:sup>\n            <jats:italic>v<\/jats:italic>\n            labeled by an open parenthesis \u201c(\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            \u201d is accompanied with an inverse edge\n            <jats:italic>v<\/jats:italic>\n            \u2192\n            <jats:sup>\n              )\n              <jats:sub>\n                <jats:italic>i<\/jats:italic>\n              <\/jats:sub>\n            <\/jats:sup>\n            <jats:italic>u<\/jats:italic>\n            labeled by the corresponding close parenthesis \u201c)\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            \u201d, and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with\n            <jats:italic>n<\/jats:italic>\n            nodes and\n            <jats:italic>m<\/jats:italic>\n            edges, the optimal bidirected Dyck-reachability algorithm computes\n            <jats:italic>all-pairs<\/jats:italic>\n            reachability information in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ) time.\n          <\/jats:p>\n          <jats:p>\n            This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. Dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) update time to achieve\n            <jats:italic>O<\/jats:italic>\n            (1) query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees.\n          <\/jats:p>\n          <jats:p>\n            Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update (\n            <jats:italic>i.e.<\/jats:italic>\n            , edge insertion and deletion) in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u00b7\u03b1(\n            <jats:italic>n<\/jats:italic>\n            )) time and support any all-pairs reachability query in\n            <jats:italic>O<\/jats:italic>\n            (1) time, where \u03b1(\n            <jats:italic>n<\/jats:italic>\n            ) is the inverse Ackermann function. We have implemented and evaluated our dynamic algorithm on an alias analysis and a context-sensitive data-dependence analysis for Java. We compare our dynamic algorithms against a straightforward approach based on the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            )-time optimal bidirected Dyck-reachability algorithm and a recent incremental Datalog solver. Experimental results show that our algorithm achieves orders of magnitude speedup over both approaches.\n          <\/jats:p>","DOI":"10.1145\/3498724","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T17:03:12Z","timestamp":1642006992000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Efficient algorithms for dynamic bidirected Dyck-reachability"],"prefix":"10.1145","volume":"6","author":[{"given":"Yuanbo","family":"Li","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kris","family":"Satya","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qirun","family":"Zhang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480945.1480946"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596527.1596530"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568243"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594299"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1640089.1640108"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.56098"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73584"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158118"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892126"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338112"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69611-7_7"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945403"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814305"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594324"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.45"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301380"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996867"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386021"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293606"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(03)00007-0"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094848"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_4"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908096"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428195"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/349214.349241"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158710"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_2_32_1","volume-title":"Applications of Logic Databases, Raghu Ramakrishnan (Ed","author":"Reps Thomas W.","unstructured":"Thomas W. Reps . 1993. Demand Interprocedural Program Analysis Using Logic Databases . In Applications of Logic Databases, Raghu Ramakrishnan (Ed .) (The Kluwer International Series in Engineering and Computer Science 296). Kluwer , 163\u2013196. Thomas W. Reps. 1993. Demand Interprocedural Program Analysis Using Logic Databases. In Applications of Logic Databases, Raghu Ramakrishnan (Ed.) (The Kluwer International Series in Engineering and Computer Science 296). Kluwer, 163\u2013196."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644172"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/42192.42193"},{"key":"e_1_2_2_38_1","volume-title":"Datalog 2.0 2019 - 3rd International Workshop on the Resurgence of Datalog in Academia and Industry (CEUR Workshop Proceedings","author":"Ryzhyk Leonid","unstructured":"Leonid Ryzhyk and Mihai Budiu . 2019. Differential Datalog . In Datalog 2.0 2019 - 3rd International Workshop on the Resurgence of Datalog in Academia and Industry (CEUR Workshop Proceedings , Vol. 2368). 56\u2013 67 . http:\/\/ceur-ws.org\/Vol-2368\/paper6.pdf Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog. In Datalog 2.0 2019 - 3rd International Workshop on the Resurgence of Datalog in Academia and Industry (CEUR Workshop Proceedings, Vol. 2368). 56\u201367. http:\/\/ceur-ws.org\/Vol-2368\/paper6.pdf"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1069774.1069785"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11562931_19"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11799573_7"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.25"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250770"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290361"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/244795.244799"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134027"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276509"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454026"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2970276.2970298"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676997"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03013-0_6"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/302405.302676"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462159"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498724","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498724","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:29Z","timestamp":1750188629000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":56,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2022,1,16]]}},"alternative-id":["10.1145\/3498724"],"URL":"https:\/\/doi.org\/10.1145\/3498724","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"2022-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}