{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:12:06Z","timestamp":1725516726086},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705826"},{"type":"electronic","value":"9783540705833"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_14","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"160-171","source":"Crossref","is-referenced-by-count":7,"title":["On Datalog vs. LFP"],"prefix":"10.1007","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","unstructured":"Open Problems List for the MathsCSP Workshop, Oxford (2006), http:\/\/www.cs.rhul.ac.uk\/home\/green\/mathscsp\/"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jcss.1995.1060","volume":"51","author":"F. Afrati","year":"1995","unstructured":"Afrati, F., Cosmadakis, S., Yannakakis, M.: On Datalog vs. Polynomial Time. Journal of Computer and System Sciences\u00a051, 177\u2013196 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR3","unstructured":"Atserias, A.: The homomorphism preservation property. In: Talk at International Workshop on Mathematics of Constraint Satisfaction, Oxford (2006)"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-73420-8_49","volume-title":"Proc. 34th International Colloquium on Automata, Languages and Programming","author":"A. Atserias","year":"2007","unstructured":"Atserias, A., Bulatov, A., Dawar, A.: Affine systems of equations and counting infinitary logic. In: Proc. 34th International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a04596, pp. 558\u2013570. Springer, Heidelberg (2007)"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1437","DOI":"10.1007\/11523468_116","volume-title":"Automata, Languages and Programming","author":"A. Atserias","year":"2005","unstructured":"Atserias, A., Dawar, A., Grohe, M.: Preservation under extensions on well-behaved finite structures. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1437\u20131449. Springer, Heidelberg (2005)"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1145\/1131342.1131344","volume":"53","author":"A. Atserias","year":"2006","unstructured":"Atserias, A., Dawar, A., Kolaitis, P.G.: On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM\u00a053, 208\u2013237 (2006)","journal-title":"Journal of the ACM"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational databases. In: Proc. 9th ACM Symp. on Theory of Computing, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"14_CR8","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: Computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing\u00a028, 57\u2013104 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Feder, T., Vardi, M.Y.: Homomorphism closed vs existential positive. In: Proc.\u00a0of the 18th IEEE Symp.\u00a0on Logic in Computer Science, pp. 311\u2013320 (2003)","DOI":"10.1109\/LICS.2003.1210071"},{"key":"14_CR11","unstructured":"Grohe, M.: Logic, graphs, and algorithms. In: Flum, J., Gr\u00e4del, E., Wilke, T. (eds.) Logic and Automata History and Perspectives, Amsterdam University Press (2007)"},{"key":"14_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W. Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Information and Control\u00a068, 86\u2013104 (1986)","journal-title":"Information and Control"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P..G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive query containment and constraint satisfaction. Journal of Computer and System Sciences\u00a061, 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic\u00a0126, 159\u2013213 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"14_CR16","volume-title":"Elementary Induction on Abstract Structures","author":"Y.N. Moschovakis","year":"1974","unstructured":"Moschovakis, Y.N.: Elementary Induction on Abstract Structures. North Holland, Amsterdam (1974)"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Rossman, B.: Existential positive types and preservation under homomorphisisms. In: 20th IEEE Symposium on Logic in Computer Science, pp. 467\u2013476 (2005)","DOI":"10.1109\/LICS.2005.16"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Proc.\u00a0of the 14th ACM Symp.\u00a0on the Theory of Computing, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:07:55Z","timestamp":1605762475000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}