{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T13:08:43Z","timestamp":1791205723479,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T00:00:00Z","timestamp":1465948800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"T\u00e9l\u00e9com ParisTech Research Chair on Big Data and Market Insights"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,15]]},"DOI":"10.1145\/2902251.2902301","type":"proceedings-article","created":{"date-parts":[[2016,6,16]],"date-time":"2016-06-16T20:16:05Z","timestamp":1466108165000},"page":"355-370","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Tractable Lineages on Treelike Instances"],"prefix":"10.1145","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"LTCI, CNRS, T\u00e9l\u00e9com ParisTech, Universit\u00e9 Paris-Saclay, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[{"name":"CRIStAL, UMR 9189, CNRS, Universit\u00e9 Lille 1, Lille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[{"name":"LTCI, CNRS, T\u00e9l\u00e9com ParisTech, Universit\u00e9 Paris-Saclay & IPAL, CNRS, NUS, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,15]]},"reference":[{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"A. Amarilli P. Bourhis and P. Senellart. Provenance circuits for trees and treelike instances (extended version). http:\/\/arxiv.org\/abs\/1511.08723 2015.  A. Amarilli P. Bourhis and P. Senellart. Provenance circuits for trees and treelike instances (extended version). http:\/\/arxiv.org\/abs\/1511.08723 2015.","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_3_2_1_7_1","volume-title":"KR","author":"Calvanese D.","year":"2000","unstructured":"D. Calvanese , G. De Giacomo , M. Lenzerini , and M. Y. Vardi . Containment of conjunctive regular path queries with inverse . In KR , 2000 . D. Calvanese, G. De Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In KR, 2000."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.031"},{"key":"e_1_3_2_1_9_1","volume-title":"UAI","author":"Chandrasekaran V.","year":"2008","unstructured":"V. Chandrasekaran , N. Srebro , and P. Harsha . Complexity of inference in graphical models . In UAI , 2008 . V. Chandrasekaran, N. Srebro, and P. Harsha. Complexity of inference in graphical models. In UAI, 2008."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591813"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559831"},{"key":"e_1_3_2_1_12_1","volume-title":"Tree automata: Techniques and applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata","author":"Comon H.","year":"2007","unstructured":"H. Comon , M. Dauchet , R. Gilleron , C. L\u00f6ding , F. Jacquemard , D. Lugiez , S. Tison , and M. Tommasi . Tree automata: Techniques and applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata , 2007 . H. Comon, M. Dauchet, R. Gilleron, C. L\u00f6ding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata: Techniques and applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata, 2007."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"e_1_3_2_1_15_1","volume-title":"Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Sci., 33(2)","author":"Courcelle B.","year":"2000","unstructured":"B. Courcelle , J. A. Makowsky , and U. Rotics . Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Sci., 33(2) , 2000 . B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Sci., 33(2), 2000."},{"key":"e_1_3_2_1_16_1","volume-title":"KR","author":"Dalvi N.","year":"2010","unstructured":"N. Dalvi , K. Schnaitter , and D. Suciu . Computing query probability with incidence algebras . In KR , 2010 . N. Dalvi, K. Schnaitter, and D. Suciu. Computing query probability with incidence algebras. In KR, 2010."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265571"},{"key":"e_1_3_2_1_20_1","author":"Darwiche A.","year":"2001","unstructured":"A. Darwiche . On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Applied Non-Classical Logics, 11(1--2) , 2001 . A. Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Applied Non-Classical Logics, 11(1--2), 2001.","journal-title":"J. Applied Non-Classical Logics, 11(1--2)"},{"key":"e_1_3_2_1_21_1","volume-title":"ICDT","author":"Deutch D.","year":"2014","unstructured":"D. Deutch , T. Milo , S. Roy , and V. Tannen . Circuits for Datalog provenance . In ICDT , 2014 . D. Deutch, T. Milo, S. Roy, and V. Tannen. Circuits for Datalog provenance. In ICDT, 2014."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"R. Diestel. Graph Theory. Springer 2005.  R. Diestel. Graph Theory. Springer 2005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594549"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17493-3_14"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.005"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735494"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/507382.507388"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_2_1_30_1","first-page":"2","author":"Grohe M.","year":"2007","unstructured":"M. Grohe . Logic, graphs, and algorithms. Logic and Automata: History and Perspectives , 2 , 2007 . M. Grohe. Logic, graphs, and algorithms. Logic and Automata: History and Perspectives, 2, 2007.","journal-title":"Logic and Automata: History and Perspectives"},{"key":"e_1_3_2_1_31_1","first-page":"258","author":"Hansel G.","year":"1964","unstructured":"G. Hansel . Nombre minimal de contacts de fermeture n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables. C. R. Acad. Sc. Paris , 258 , 1964 . G. Hansel. Nombre minimal de contacts de fermeture n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables. C. R. Acad. Sc. Paris, 258, 1964.","journal-title":"Acad. Sc. Paris"},{"key":"e_1_3_2_1_32_1","author":"Huang C.","year":"1996","unstructured":"C. Huang and A. Darwiche . Inference in belief networks: A procedural guide. Int. J. Approximate Reasoning , 1996 . C. Huang and A. Darwiche. Inference in belief networks: A procedural guide. Int. J. Approximate Reasoning, 1996.","journal-title":"Inference in belief networks: A procedural guide. Int. J. Approximate Reasoning"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1886"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274603"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9392-5"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789697"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1860967.1861015"},{"key":"e_1_3_2_1_40_1","author":"Lauritzen S. L.","year":"1988","unstructured":"S. L. Lauritzen and D. J. Spiegelhalter . Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society. Series B , 1988 . S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society. Series B, 1988.","journal-title":"J. Royal Statistical Society. Series B"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00080-X"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00449-8"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334193"},{"key":"e_1_3_2_1_44_1","volume-title":"Can you beat treewidth? Theory of Computing, 6(1)","author":"Marx D.","year":"2010","unstructured":"D. Marx . Can you beat treewidth? Theory of Computing, 6(1) , 2010 . D. Marx. Can you beat treewidth? Theory of Computing, 6(1), 2010."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/35517"},{"key":"e_1_3_2_1_52_1","volume-title":"Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci., 384(1)","author":"Xia M.","year":"2007","unstructured":"M. Xia , P. Zhang , and W. Zhao . Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci., 384(1) , 2007 . M. Xia, P. Zhang, and W. Zhao. Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci., 384(1), 2007."}],"event":{"name":"SIGMOD\/PODS'16: International Conference on Management of Data","location":"San Francisco California USA","acronym":"SIGMOD\/PODS'16","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2902251.2902301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2902251.2902301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:59Z","timestamp":1750222499000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2902251.2902301"}},"subtitle":["Limits and Extensions"],"short-title":[],"issued":{"date-parts":[[2016,6,15]]},"references-count":51,"alternative-id":["10.1145\/2902251.2902301","10.1145\/2902251"],"URL":"https:\/\/doi.org\/10.1145\/2902251.2902301","relation":{},"subject":[],"published":{"date-parts":[[2016,6,15]]},"assertion":[{"value":"2016-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}