{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:33:24Z","timestamp":1725824004223},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_34","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T03:46:47Z","timestamp":1434685607000},"page":"427-439","source":"Crossref","is-referenced-by-count":4,"title":["Containment of Monadic Datalog Programs via Bounded Clique-Width"],"prefix":"10.1007","author":[{"given":"Miko\u0142aj","family":"Boja\u0144czyk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Filip","family":"Murlak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Witkowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Bourhis, P., Muscholl, A., Wu, Z.: Recursive queries on trees and data trees. In: ICDT 2013, pp. 93\u2013104 (2013)","DOI":"10.1145\/2448496.2448509"},{"key":"34_CR2","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley (1995)"},{"key":"34_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-540-85238-4_10","volume-title":"Mathematical Foundations of Computer Science 2008","author":"H Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, H., Martens, W., Schwentick, T.: Optimizing conjunctive queries over trees using schema information. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 132\u2013143. Springer, Heidelberg (2008)"},{"issue":"6","key":"34_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"Ceri, S., Gottlob, G., Tanca, L.: Logic programming and databases. Springer-Verlag New York Inc. (1990)","DOI":"10.1007\/978-3-642-83952-8"},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC 1977, pp. 77\u201390. ACM, New York (1977)","DOI":"10.1145\/800105.803397"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"Cosmadakis, S.S., Gaifman, H., Kanellakis, P.C., Vardi, M.Y.: Decidable optimization problems for database logic programs (preliminary report). In: STOC 1988, pp. 477\u2013490 (1988)","DOI":"10.1145\/62212.62259"},{"issue":"1","key":"34_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0304-3975(51)90009-6","volume":"78","author":"B Courcelle","year":"1991","unstructured":"Courcelle, B.: Recursive queries and context-free graph grammars. Theor. Comput. Sci. 78(1), 217\u2013244 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"34_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"34_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Applied Mathematics 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"34_CR11","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J Doner","year":"1970","unstructured":"Doner, J.: Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4(5), 406\u2013451 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"Figueira, D.: Satisfiability of downward XPath with data equality tests. In: PODS 2009, pp. 197\u2013206 (2009)","DOI":"10.1145\/1559795.1559827"},{"issue":"1","key":"34_CR13","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/962446.962450","volume":"51","author":"G Gottlob","year":"2004","unstructured":"Gottlob, G., Koch, C.: Monadic datalog and the expressive power of languages for web information extraction. J. ACM 51(1), 74\u2013113 (2004)","journal-title":"J. ACM"},{"issue":"1","key":"34_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1838552.1838555","volume":"12","author":"G Gottlob","year":"2010","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Monadic datalog over finite structures of bounded treewidth. ACM Trans. Comput. Log. 12(1), 3 (2010)","journal-title":"ACM Trans. Comput. Log."},{"issue":"1","key":"34_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00224-003-1112-8","volume":"37","author":"M Grohe","year":"2004","unstructured":"Grohe, M., Tur\u00e1n, G.: Learnability and definability in trees and similar structures. Theory Comput. Syst. 37(1), 193\u2013220 (2004)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"34_CR16","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012\u20131032 (2008)","journal-title":"SIAM J. Comput."},{"key":"34_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/978-3-662-44522-8_36","volume-title":"Mathematical Foundations of Computer Science 2014","author":"F Mazowiecki","year":"2014","unstructured":"Mazowiecki, F., Murlak, F., Witkowski, A.: Monadic datalog and regular tree pattern queries. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 426\u2013437. Springer, Heidelberg (2014)"},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods in Computer Science 2(3) (2006)","DOI":"10.2168\/LMCS-2(3:1)2006"},{"issue":"3","key":"34_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0743-1066(93)90040-N","volume":"15","author":"O Shmueli","year":"1993","unstructured":"Shmueli, O.: Equivalence of datalog queries is undecidable. J. Log. Program. 15(3), 231\u2013241 (1993)","journal-title":"J. Log. Program."},{"issue":"1","key":"34_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"JW Thatcher","year":"1968","unstructured":"Thatcher, J.W., Wright, J.B.: Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory 2(1), 57\u201381 (1968)","journal-title":"Mathematical Systems Theory"},{"key":"34_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1007\/BFb0055090","volume-title":"Automata, Languages and Programming","author":"MY Vardi","year":"1998","unstructured":"Vardi, M.Y.: Reasoning about the past with two-way automata. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, p. 628. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T03:15:50Z","timestamp":1559186150000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}