{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:10:50Z","timestamp":1777889450449,"version":"3.51.4"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T00:00:00Z","timestamp":1530748800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Austrian Science Fund","award":["P23499-N23"],"award-info":[{"award-number":["P23499-N23"]}]},{"name":"FWF NFN","award":["S11407-N23(RiSE\/SHiNE)"],"award-info":[{"award-number":["S11407-N23(RiSE\/SHiNE)"]}]},{"name":"ERC","award":["279307: Graph Games"],"award-info":[{"award-number":["279307: Graph Games"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"<jats:p>\n            We study algorithmic questions wrt algebraic path properties in concurrent systems, where the transitions of the system are labeled from a complete, closed semiring. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the\n            <jats:italic>one-time<\/jats:italic>\n            preprocessing and for\n            <jats:italic>each individual<\/jats:italic>\n            query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.\n          <\/jats:p>\n          <jats:p>Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.<\/jats:p>","DOI":"10.1145\/3210257","type":"journal-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T19:19:10Z","timestamp":1530818350000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components"],"prefix":"10.1145","volume":"40","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir Kafshdar","family":"Goharshady","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/646229.681725"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264320"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90039-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/646242.681417"},{"key":"e_1_2_1_11_1","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender Hans L.","year":"1993","unstructured":"Hans L. Bodlaender. 1993. A tourist guide through treewidth. Acta Cybern. 11, 1 (1993), 1--13.","journal-title":"Acta Cybern."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_28"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604137"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85778-5_4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24841-5_6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21668-3_11"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429085"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805950.1805953"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837624"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676979"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Computer-Aided Verification (CAV\u201913)","author":"Chatterjee K.","unstructured":"K. Chatterjee and J. Lacki. 2013. Faster algorithms for Markov decision processes with low treewidth. In Proceedings of the International Conference on Computer-Aided Verification (CAV\u201913)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676968"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010016"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375620"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Brouno Courcelle. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science Vol. B. MIT Press Cambridge MA.","DOI":"10.5555\/114891.114896"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987211.1987222"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199461"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040291.1040292"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.21"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429086"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763507.1763521"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155349"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"J. Gustedt O. Maehle and J. Telle. 2002. The treewidth of java programs. In Algorithm Engineering and Experiments. Springer.","DOI":"10.5555\/646680.702325"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/646732.701290"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/222132.222146"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-013-0274-1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1595696.1595701"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512945"},{"key":"e_1_2_1_49_1","volume-title":"Representation of events in nerve nets and finite automata. Automata Studies","author":"Kleene S. C.","year":"1956","unstructured":"S. C. Kleene. 1956. Representation of events in nerve nets and finite automata. Automata Studies (1956)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229545"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","unstructured":"Philipp Klaus Krause. 2013. Optimal register allocation in polynomial time. In Compiler Construction Ranjit Jhala and Koen De Bosschere (Eds.). 10.1007\/978-3-642-37051-9_1","DOI":"10.1007\/978-3-642-37051-9_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792762"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31424-7_32"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-009-0078-9"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792761"},{"key":"e_1_2_1_56_1","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler Eugene","year":"1976","unstructured":"Eugene Lawler. 1976. Combinatorial Optimization: Networks and Matroids. Saunders College Publishing."},{"key":"e_1_2_1_57_1","volume-title":"Algebraic structures for transitive closure. Theoretical Computer Science","author":"Lehmann Daniel J.","year":"1977","unstructured":"Daniel J. Lehmann. 1977. Algebraic structures for transitive closure. Theoretical Computer Science (1977)."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926419"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_8"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45069-6_7"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31980-1_7"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129734"},{"key":"e_1_2_1_63_1","volume-title":"Applications of Logic Databases.","author":"Reps Thomas W.","unstructured":"Thomas W. Reps. 1995. Demand interprocedural program analysis using logic databases. In Applications of Logic Databases. Vol. 296."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/271338.271343"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","unstructured":"Neil Robertson and P. D. Seymour. 1984. Graph minors. III. Planar tree-width. J. Combin. Theor. Ser. B (1984).","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","unstructured":"Mooly Sagiv Thomas Reps and Susan Horwitz. 1996. Precise interprocedural dataflow analysis with applications to constant propagation. Theor. Comput. Sci. (1996). 10.1016\/0304-3975(96)00072-2","DOI":"10.1016\/0304-3975(96)00072-2"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85114-1_19"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_2_1_70_1","volume-title":"Proceedings of the Centre for Advanced Studies Conference (CASCON\u201999)","author":"Vall\u00e9e-Rai Raja","year":"1999","unstructured":"Raja Vall\u00e9e-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. 1999. Soot - A java bytecode optimization framework. In Proceedings of the Centre for Advanced Studies Conference (CASCON\u201999). IBM Press."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1054010"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001420.2001440"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012962649700036X"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/502874.502888"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210257","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3210257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:49Z","timestamp":1750210789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3210257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,5]]},"references-count":75,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3210257"],"URL":"https:\/\/doi.org\/10.1145\/3210257","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,5]]},"assertion":[{"value":"2016-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}