{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:47Z","timestamp":1773481787841,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476659","type":"print"},{"value":"9783662476666","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_5","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"56-68","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Provenance Circuits for Trees and Treelike Instances"],"prefix":"10.1007","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[]},{"given":"Pierre","family":"Bourhis","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Senellart","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"5_CR1","unstructured":"Amsterdamer, Y., Deutch, D., Tannen, V.: On the limitations of provenance for queries with difference. In: TaPP (2011)"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2) (1991)","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"5_CR3","unstructured":"Baget, J., Lecl\u00e8re, M., Mugnier, M.: Walking the decidability line for rules with existential variables. In: KR (2010)"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6) (1996)","DOI":"10.1137\/S0097539793251219"},{"key":"5_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/978-3-642-33475-7_4","volume-title":"Theoretical Computer Science","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L.: Probabilistic inference and monadic second order logic. In: Baeten, J.C.M., Ball, T., de Boer, F.S. (eds.) TCS 2012. LNCS, vol. 7604, pp. 43\u201356. Springer, Heidelberg (2012)"},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-662-43951-7_3","volume-title":"Automata, Languages, and Programming","author":"M Boja\u0144czyk","year":"2014","unstructured":"Boja\u0144czyk, M.: Transducers with origin information. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 26\u201337. Springer, Heidelberg (2014)"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Cheney, J., Chiticariu, L., Tan, W.C.: Provenance in databases: Why, how, and where. Foundations and Trends in Databases 1(4) (2009)","DOI":"10.1561\/1900000006"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Running tree automata on probabilistic XML. In: PODS (2009)","DOI":"10.1145\/1559795.1559831"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1) (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Dalvi, N., Suciu, D.: Efficient query evaluation on probabilistic databases. VLDBJ 16(4) (2007)","DOI":"10.1007\/s00778-006-0004-3"},{"key":"5_CR11","unstructured":"Deutch, D., Milo, T., Roy, S., Tannen, V.: Circuits for Datalog provenance. In: ICDT (2014)"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6) (2002)","DOI":"10.1145\/602220.602222"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Foster, J.N., Green, T.J., Tannen, V.: Annotated XML: queries and provenance. In: PODS (2008)","DOI":"10.1145\/1376916.1376954"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Monadic Datalog over finite structures of bounded treewidth. TOCL 12(1) (2010)","DOI":"10.1145\/1838552.1838555"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E.: Efficient evaluation methods for guarded logics and Datalog LITE. In: LPAR (2000)","DOI":"10.1007\/3-540-48660-7_3"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Hirsch, C., Otto, M.: Back and forth between guarded and modal logics. TOCL 3(3) (2002)","DOI":"10.1145\/507382.507388"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Green, T.J., Karvounarakis, G., Tannen, V.: Provenance semirings. In: PODS (2007)","DOI":"10.1145\/1265530.1265535"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Jha, A.K., Suciu, D.: On the tractability of query compilation and bounded treewidth. In: ICDT (2012)","DOI":"10.1145\/2274576.2274603"},{"key":"5_CR19","series-title":"Studies in Fuzziness and Soft Computing","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-642-37509-5_3","volume-title":"Advances in Probabilistic Databases for Uncertain Information Management","author":"B Kimelfeld","year":"2013","unstructured":"Kimelfeld, B., Senellart, P.: Probabilistic XML: models and complexity. In: Ma, Z., Yan, L. (eds.) Advances in Probabilistic Databases. STUDFUZZ, vol. 304, pp. 39\u201366. Springer, Heidelberg (2013)"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society, Series B (1988)","DOI":"10.1111\/j.2517-6161.1988.tb01721.x"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Meyer, A.R.: Weak monadic second order theory of succesor is not elementary-recursive. In: Logic Colloquium (1975)","DOI":"10.1007\/BFb0064872"},{"key":"5_CR22","volume-title":"Counting and enumeration problems with bounded treewidth","author":"R Pichler","year":"2010","unstructured":"Pichler, R., R\u00fcmmele, S., Woltran, S.: Counting and enumeration problems with bounded treewidth. Artificial Intelligence, and Reasoning, In Logic for Programming (2010)"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3) (1986)","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Roy, S., Perduca, V., Tannen, V.: Faster query answering in probabilistic databases using read-once functions. In: ICDT (2011)","DOI":"10.1145\/1938551.1938582"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Sen, P., Deshpande, A., Getoor, L.: Read-once functions and query evaluation in probabilistic databases. PVLDB 3(1\u20132) (2010)","DOI":"10.14778\/1920841.1920975"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Suciu, D., Olteanu, D., R\u00e9, C., Koch, C.: Probabilistic Databases. Morgan & Claypool (2011)","DOI":"10.1007\/978-3-031-01879-4"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Math. systems theory 2(1) (1968)","DOI":"10.1007\/BF01691346"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:03:38Z","timestamp":1748459018000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}