{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T07:30:49Z","timestamp":1789716649911,"version":"4.0.1"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,5,9]],"date-time":"2017-05-09T00:00:00Z","timestamp":1494288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"T\u00e9l\u00e9com ParisTech","award":["Research Chair on Big Data and Market Insights"],"award-info":[{"award-number":["Research Chair on Big Data and Market Insights"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,5,9]]},"DOI":"10.1145\/3034786.3056121","type":"proceedings-article","created":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T18:09:00Z","timestamp":1494439740000},"page":"217-232","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Conjunctive Queries on Probabilistic Graphs"],"prefix":"10.1145","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mika\u00ebl","family":"Monet","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay & Inria Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[{"name":"\u00c9cole normale sup\u00e9rieure, PSL Research University & Inria Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,5,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"AMW","author":"Amarilli A.","year":"2014","unstructured":"A. Amarilli .hrefhttp:\/\/ceur-ws.org\/Vol-1189\/paper_2. pdfThe possibility problem for probabilistic XML . In AMW , 2014 . A. Amarilli.hrefhttp:\/\/ceur-ws.org\/Vol-1189\/paper_2.pdfThe possibility problem for probabilistic XML. In AMW, 2014."},{"key":"e_1_3_2_1_2_1","volume-title":"ICDT","author":"Amarilli A.","year":"2017","unstructured":"A. Amarilli , P. Bourhis , M. Monet , and P. Senellart . Combined tractability of query evaluation via tree automata and cycluits . In ICDT , 2017 . A. Amarilli, P. Bourhis, M. Monet, and P. Senellart. Combined tractability of query evaluation via tree automata and cycluits. In ICDT, 2017."},{"key":"e_1_3_2_1_3_1","volume-title":"Combined tractability of query evaluation via tree automata and cycluits (extended version). ArXiv e-prints","author":"Amarilli A.","year":"2017","unstructured":"A. Amarilli , P. Bourhis , M. Monet , and P. Senellart . Combined tractability of query evaluation via tree automata and cycluits (extended version). ArXiv e-prints , 2017 . https:\/\/arxiv.org\/abs\/1612.04203v1. Extended version ofciteamarilli2017combined. A. Amarilli, P. Bourhis, M. Monet, and P. Senellart. Combined tractability of query evaluation via tree automata and cycluits (extended version). ArXiv e-prints, 2017. https:\/\/arxiv.org\/abs\/1612.04203v1. Extended version ofciteamarilli2017combined."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_5"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902301"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902301"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745760"},{"key":"e_1_3_2_1_9_1","volume-title":"CSUR","author":"Benedikt M.","year":"2009","unstructured":"M. Benedikt and C. Koch . hrefhttps:\/\/infoscience.epfl.ch\/record\/166852\/files\/25-leashed.pdfXPath leashed . CSUR , 2009 . M. Benedikt and C. Koch.hrefhttps:\/\/infoscience.epfl.ch\/record\/166852\/files\/25-leashed.pdfXPath leashed. CSUR, 2009."},{"key":"e_1_3_2_1_10_1","volume-title":"ArXiv e-prints","author":"Brault-Baron J.","year":"2014","unstructured":"J. Brault-Baron .hrefhttps:\/\/arxiv.org\/abs\/1403.7076 Hypergraph acyclicity revisited. ArXiv e-prints , 2014 . J. Brault-Baron.hrefhttps:\/\/arxiv.org\/abs\/1403.7076Hypergraph acyclicity revisited. ArXiv e-prints, 2014."},{"key":"e_1_3_2_1_11_1","volume-title":"STACS","author":"Brault-Baron J.","year":"2015","unstructured":"J. Brault-Baron , F. Capelli , and S. Mengel . hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2015\/4963\/pdf\/lipics-vol30-stacs2015-complete.pdfUnderstanding model counting for \u03b2-acyclic CNF-formulas . In STACS , 2015 . J. Brault-Baron, F. Capelli, and S. Mengel.hrefhttp:\/\/drops.dagstuhl.de\/opus\/volltexte\/2015\/4963\/pdf\/lipics-vol30-stacs2015-complete.pdfUnderstanding model counting for \u03b2-acyclic CNF-formulas. In STACS, 2015."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_3_2_1_13_1","volume-title":"hrefhttp:\/\/pages.cs.wisc.edu\/ jyc\/papers\/interpolation08.pdfHolographic reduction, interpolation and hardness. Computational Complexity, 21(4)","author":"Cai J.","year":"2008","unstructured":"J. Cai , P. Lu , and M. Xia . hrefhttp:\/\/pages.cs.wisc.edu\/ jyc\/papers\/interpolation08.pdfHolographic reduction, interpolation and hardness. Computational Complexity, 21(4) , 2008 . Preprint of citecai2012holographic. J. Cai, P. Lu, and M. Xia.hrefhttp:\/\/pages.cs.wisc.edu\/ jyc\/papers\/interpolation08.pdfHolographic reduction, interpolation and hardness. Computational Complexity, 21(4), 2008. Preprint ofcitecai2012holographic."},{"key":"e_1_3_2_1_14_1","volume-title":"Holographic reduction, interpolation and hardness. Computational Complexity, 21(4)","author":"Cai J.","year":"2012","unstructured":"J. Cai , P. Lu , and M. Xia . Holographic reduction, interpolation and hardness. Computational Complexity, 21(4) , 2012 . J. Cai, P. Lu, and M. Xia. Holographic reduction, interpolation and hardness. Computational Complexity, 21(4), 2012."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3032027.3032068"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559831"},{"key":"e_1_3_2_1_17_1","volume-title":"Tree automata: Techniques and applications","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 , 2007 . Available from http:\/\/www.grappa.univ-lille3.fr\/tata. H. Comon, M. Dauchet, R. Gilleron, C. L\u00f6ding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata: Techniques and applications, 2007. Available from http:\/\/www.grappa.univ-lille3.fr\/tata."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.22"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_3_2_1_21_1","author":"Darwiche A.","year":"2001","unstructured":"A. Darwiche .hrefhttps:\/\/arxiv.org\/abs\/cs\/0003044 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.hrefhttps:\/\/arxiv.org\/abs\/cs\/0003044On 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_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131345"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90294-K"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402741"},{"key":"e_1_3_2_1_27_1","volume-title":"Advances in Probabilistic Databases for Uncertain Information Management","author":"Kimelfeld B.","year":"2013","unstructured":"B. Kimelfeld and P. Senellart . hrefhttp:\/\/pierre.senellart.com\/publications\/kimelfeld2013probabilistic.pdfProbabilistic XML string: models and complexity . In Z. Ma and L. Yan, editors, Advances in Probabilistic Databases for Uncertain Information Management . Springer , 2013 . B. Kimelfeld and P. Senellart.hrefhttp:\/\/pierre.senellart.com\/publications\/kimelfeld2013probabilistic.pdfProbabilistic XML string: models and complexity. In Z. Ma and L. Yan, editors, Advances in Probabilistic Databases for Uncertain Information Management. Springer, 2013."},{"key":"e_1_3_2_1_28_1","author":"Odagiri S.","year":"2014","unstructured":"S. Odagiri and H. Goto . On the greatest number of paths and maximal paths for a class of directed acyclic graphs. IEICE Trans. Fundamentals, E97-A(6) , 2014 . S. Odagiri and H. Goto. On the greatest number of paths and maximal paths for a class of directed acyclic graphs. IEICE Trans. Fundamentals, E97-A(6), 2014.","journal-title":"IEICE Trans. Fundamentals, E97-A(6)"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_3_2_1_30_1","volume-title":"Birkh\u00e4user","author":"Schr\u00f6der B.","year":"2016","unstructured":"B. Schr\u00f6der . Ordered Sets . Birkh\u00e4user , second edition, 2016 . B. Schr\u00f6der. Ordered Sets. Birkh\u00e4user, second edition, 2016."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"R. Stanley. Enumerative Combinatorics volume 1. Cambridge University Press 1997.  R. Stanley. Enumerative Combinatorics volume 1. Cambridge University Press 1997.","DOI":"10.1017\/CBO9780511805967"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"},{"key":"e_1_3_2_1_35_1","unstructured":"T. Williams. Complexity of counting the number of edge covers of a graph. http:\/\/cstheory.stackexchange.com\/q\/21309 2014.  T. Williams. Complexity of counting the number of edge covers of a graph. http:\/\/cstheory.stackexchange.com\/q\/21309 2014."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286831.1286840"}],"event":{"name":"SIGMOD\/PODS'17: International Conference on Management of Data","location":"Chicago Illinois USA","acronym":"SIGMOD\/PODS'17","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3034786.3056121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3034786.3056121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:50:05Z","timestamp":1750218605000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3034786.3056121"}},"subtitle":["Combined Complexity"],"short-title":[],"issued":{"date-parts":[[2017,5,9]]},"references-count":36,"alternative-id":["10.1145\/3034786.3056121","10.1145\/3034786"],"URL":"https:\/\/doi.org\/10.1145\/3034786.3056121","relation":{},"subject":[],"published":{"date-parts":[[2017,5,9]]},"assertion":[{"value":"2017-05-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}