{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T19:01:47Z","timestamp":1743102107623,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540885931"},{"type":"electronic","value":"9783540885948"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-88594-8_3","type":"book-chapter","created":{"date-parts":[[2008,10,20]],"date-time":"2008-10-20T13:36:43Z","timestamp":1224509803000},"page":"48-76","source":"Crossref","is-referenced-by-count":4,"title":["The Relational Polynomial-Time Hierarchy and Second-Order Logic"],"prefix":"10.1007","author":[{"given":"Flavio A.","family":"Ferrarotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 M.","family":"Turull Torres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A.K. Chandra","year":"1980","unstructured":"Chandra, A.K., Harel, D.: Computable queries for relational data bases. J. Comput. Syst. Sci.\u00a021, 156\u2013178 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1145\/73721.73755","volume-title":"Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"R. Hull","year":"1989","unstructured":"Hull, R., Su, J.: Untyped sets, invention, and computable queries. In: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, pp. 347\u2013359. ACM Press, New York (1989)"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/103418.103444","volume-title":"Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing","author":"S. Abiteboul","year":"1991","unstructured":"Abiteboul, S., Vianu, V.: Generic computation and its complexity. In: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, pp. 209\u2013219. ACM Press, New York (1991)"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1006\/jcss.1995.1025","volume":"50","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Vianu, V.: Computing with first-order logic. J. Comput. Syst. Sci.\u00a050, 309\u2013335 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/inco.1998.2701","volume":"143","author":"S. Abiteboul","year":"1998","unstructured":"Abiteboul, S., Papadimitriou, C.H., Vianu, V.: Reflective relational machines. Inf. Comput.\u00a0143, 110\u2013136 (1998)","journal-title":"Inf. Comput."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/256292.256295","volume":"44","author":"S. Abiteboul","year":"1997","unstructured":"Abiteboul, S., Vardi, M.Y., Vianu, V.: Fixpoint logics, relational machines, and computational complexity. J. ACM\u00a044, 30\u201356 (1997)","journal-title":"J. ACM"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0304-3975(95)00027-T","volume":"149","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Vardi, M.Y., Vianu, V.: Computing with infinitary logic. Theor. Comput. Sci.\u00a0149, 101\u2013128 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/inco.1998.2703","volume":"143","author":"A. Dawar","year":"1998","unstructured":"Dawar, A.: A restricted second order logic for finite structures. Inf. Comput.\u00a0143, 154\u2013174 (1998)","journal-title":"Inf. Comput."},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci.\u00a03, 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR10","series-title":"Perspectives in Mathematical Logic","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Perspectives in Mathematical Logic. Springer, Heidelberg (1999)","edition":"2"},{"key":"3_CR11","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1994","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Redwood City (1994)"},{"key":"3_CR12","series-title":"Texts in Theoretical Computer Science, EATCS","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements Of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements Of Finite Model Theory. Texts in Theoretical Computer Science, EATCS. Springer, Heidelberg (2004)"},{"key":"3_CR13","first-page":"46","volume-title":"Proceedings of the 7th Annual IEEE Symposium on Logic in Computer Science","author":"P.G. Kolaitis","year":"1992","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Fixpoint logic vs. infinitary logic in finite-model theory. In: Proceedings of the 7th Annual IEEE Symposium on Logic in Computer Science, Santa Cruz, California, USA, pp. 46\u201357. IEEE Computer Society Press, Los Alamitos (1992)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P.G. Kolaitis","year":"1992","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Infinitary logics and 0-1 laws. Inform. and Comput.\u00a098, 258\u2013294 (1992)","journal-title":"Inform. and Comput."},{"key":"3_CR15","unstructured":"Dawar, A.: Feasible Computation Through Model Theory. PhD thesis, University of Pennsylvania, Philadelphia (1993)"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/inco.1995.1084","volume":"119","author":"A. Dawar","year":"1995","unstructured":"Dawar, A., Lindell, S., Weinstein, S.: Infinitary logic and inductive definability over finite structures. Inf. Comput.\u00a0119, 160\u2013175 (1995)","journal-title":"Inf. Comput."},{"key":"3_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded variable logics and counting \u2013 A study in finite models","author":"M. Otto","year":"1997","unstructured":"Otto, M.: Bounded variable logics and counting \u2013 A study in finite models, vol.\u00a09. Springer, Heidelberg (1997)"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1023\/A:1013132216581","volume":"33","author":"J.M. Turull Torres","year":"2001","unstructured":"Turull Torres, J.M.: A study of homogeneity in relational databases. Ann. Math. Artif. Intell.\u00a033, 379\u2013414 (2001), Also see erratum in 42(4), 443\u2013444 (2004)","journal-title":"Ann. Math. Artif. Intell."}],"container-title":["Lecture Notes in Computer Science","Semantics in Data and Knowledge Bases"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88594-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T16:36:58Z","timestamp":1684600618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-88594-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540885931","9783540885948"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88594-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}