{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T08:56:04Z","timestamp":1781859364046,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T00:00:00Z","timestamp":1421193600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["S11405, P23499-N23"],"award-info":[{"award-number":["S11405, P23499-N23"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","award":["Faculty Fellows Award"],"award-info":[{"award-number":["Faculty Fellows Award"]}],"id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["279307: Graph Games"],"award-info":[{"award-number":["279307: Graph Games"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,1,14]]},"DOI":"10.1145\/2676726.2676979","type":"proceedings-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T08:51:05Z","timestamp":1418979065000},"page":"97-109","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth"],"prefix":"10.1145","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prateesh","family":"Goyal","sequence":"additional","affiliation":[{"name":"IIT Bombay, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,1,14]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Optimal preprocessing for answering on-line product queries. Technical report","author":"Alon N.","year":"1987","unstructured":"N. Alon and B. Schieber. Optimal preprocessing for answering on-line product queries. Technical report, Tel Aviv University, 1987."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1075382.1075387"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.017"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90039-3"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/647674.731644"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646242.681417"},{"key":"e_1_3_2_2_10_1","volume-title":"Acta Cybern.","author":"Bodlaender H. L.","year":"1993","unstructured":"H. L. Bodlaender. A tourist guide through treewidth. Acta Cybern., 1993."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/12276.13327"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958031.2958116"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.30"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2676968"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328438.1328460"},{"key":"e_1_3_2_2_16_1","volume-title":"Part I: Sequential Algorithms. Algorithmica","author":"Chaudhuri S.","year":"1995","unstructured":"S. Chaudhuri and C. D. Zaroliagis. Shortest Paths in Digraphs of Small Treewidth. Part I: Sequential Algorithms. Algorithmica, 1995."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/500824"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/114891.114896"},{"key":"e_1_3_2_2_19_1","volume-title":"IFIP Conf. on Formal Description of Programming Concepts","author":"Cousot P.","year":"1977","unstructured":"P. Cousot and R. Cousot. Static determination of dynamic properties of recursive procedures. In E. Neuhold, editor, IFIP Conf. on Formal Description of Programming Concepts, 1977."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.21"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1971.4"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647570.729779"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155099"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646680.702325"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010021"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/222132.222146"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"crossref","unstructured":"T. Kloks. Treewidth Computations and Approximations. LNCS. Springer 1994.","DOI":"10.1007\/BFb0045375"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/647471.727286"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229545"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483707"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/99583.99599"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1449764.1449792"},{"key":"e_1_3_2_2_34_1","volume-title":"CAV","author":"Obdrz\u00e1lek J.","year":"2003","unstructured":"J. Obdrz\u00e1lek. Fast mu-calculus model checking when tree-width is bounded. In CAV, 2003."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129734"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.009"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781794.1781799"},{"key":"e_1_3_2_2_39_1","series-title":"Series B","volume-title":"Graph minors. iii. planar tree-width. Journal of Combinatorial Theory","author":"Robertson N.","year":"1984","unstructured":"N. Robertson and P. Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 1984."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00072-2"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094811.1094817"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_3_2_2_43_1","volume-title":"CASCON '99","author":"Vall\u00e9e-Rai R.","year":"1999","unstructured":"R. Vall\u00e9e-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan. Soot - a java bytecode optimization framework. In CASCON '99. IBM Press, 1999."},{"key":"e_1_3_2_2_44_1","volume-title":"Computing treewidth with libtw. Technical report","author":"van Dijk T.","year":"2006","unstructured":"T. van Dijk, J.-P. van den Heuvel, and W. Slob. Computing treewidth with libtw. Technical report, University of Utrecht, 2006."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594328"}],"event":{"name":"POPL '15: The 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","location":"Mumbai India","acronym":"POPL '15","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2676726.2676979","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2676726.2676979","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T08:35:37Z","timestamp":1781858137000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2676726.2676979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,14]]},"references-count":45,"alternative-id":["10.1145\/2676726.2676979","10.1145\/2676726"],"URL":"https:\/\/doi.org\/10.1145\/2676726.2676979","relation":{"is-identical-to":[{"id-type":"doi","id":"10.1145\/2775051.2676979","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2015,1,14]]},"assertion":[{"value":"2015-01-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}