{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:16Z","timestamp":1742617156899,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540560395"},{"type":"electronic","value":"9783540473602"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56039-4_36","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:55:30Z","timestamp":1330253730000},"page":"113-123","source":"Crossref","is-referenced-by-count":6,"title":["Computing with infinitary logic"],"prefix":"10.1007","author":[{"given":"Serge","family":"Abiteboul","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F., S.S. Cosmadakis, M. Yannakakis, On Datalog vs. polynomial time, Proc. 10th ACM Symp. on Principles of Database Systems (1991), 13\u201325.","DOI":"10.1145\/113413.113415"},{"issue":"1","key":"7_CR2","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"Abiteboul, S., V. Vianu, Datalog extensions for database updates and queries, J. Computer and System Sciences 43:1 (1991), 62\u2013124.","journal-title":"J. Computer and System Sciences"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., V. Vianu, Generic computation and its complexity, Proc. 23rd ACM Symposium on Theory of Computing (1991), 209\u2013219.","DOI":"10.1145\/103418.103444"},{"key":"7_CR4","unstructured":"Abiteboul, S., V. Vianu, Computing with first-order logic, to appear in J. Computer and System Sciences."},{"key":"7_CR5","unstructured":"Abiteboul, S., M.Y. Vardi, V. Vianu, Fixpoint logics, relational machines, and computational complexity, to appear in Proc. 7th IEEE Conf. on Structure in Complexity Theory (1992)."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Barwise, J., Admissible Sets and Structures, Springer-Verlag, 1975.","DOI":"10.1007\/978-3-662-11035-5"},{"key":"7_CR7","doi-asserted-by":"crossref","first-page":"292","DOI":"10.2307\/2272133","volume":"42","author":"J. Barwise","year":"1977","unstructured":"Barwise, J., On Moschovakis closure ordinals, J. Symbolic Logic, 42 (1977), 292\u2013296.","journal-title":"J. Symbolic Logic"},{"key":"7_CR8","unstructured":"Barwise, J., S. Feferman (eds.), Model-Theoretic Logics, Springer-Verlag, 1985."},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, N. Immerman, and H. Straubing, On uniformity within NC1, J. Computer and System Sciences 41 (1990), 274\u2013306.","journal-title":"J. Computer and System Sciences"},{"issue":"2","key":"7_CR10","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A.K. Chandra","year":"1980","unstructured":"Chandra, A.K., D. Harel, Computable Queries for Relational Databases, J. Computer and System Sciences 21:2 (1980), 156\u2013178.","journal-title":"J. Computer and System Sciences"},{"issue":"1","key":"7_CR11","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A.K. Chandra","year":"1982","unstructured":"Chandra, A.K., D. Harel, Structure and Complexity of Relational Queries, J. Computer and System Sciences 25:1 (1982), 99\u2013128.","journal-title":"J. Computer and System Sciences"},{"key":"7_CR12","unstructured":"Dawar, A., S. Lindell and S. Weinstein, Infinitary logic and inductive definability over finite structures, Technical Report, Univ. of Pennsylvania, 1991."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Fagin R., Finite-Model Theory\u2014a Personal Perspective, Proc. 3rd Int'l. Conf. on Database Theory, Springer-Verlag, Lecture Notes in Computer Science 470 (1990), 3\u201324, to appear in Theoretical Computer Science.","DOI":"10.1007\/3-540-53507-1_67"},{"key":"7_CR14","unstructured":"Hopcroft J.E., J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979."},{"key":"7_CR15","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 68 (1986), 86\u2013104.","journal-title":"Information and Control"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"Kanellakis, P.C., Elements of Relational Database Theory, Handbook of Theoretical Computer Science (J. van Leeuwen, A.R. Meyer, N. Nivat, M.S. Paterson, and D. Perrin, eds.), Vol. B, Chapter 17, North-Holland, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., M.Y. Vardi, The decision problem for the probabilities of higher-order properties, Proc. 19th ACM Symp. on Theory of Computing (1987), 425\u2013435.","DOI":"10.1145\/28395.28441"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., M.Y. Vardi, On the expressive power of Datalog: tools and a case study, Proc. 9th ACM Symp. on Principles of Database Systems (1990), 61\u201371. To appear in J. Computer and System Sciences.","DOI":"10.1145\/298514.298542"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., M.Y. Vardi, 0\u20131 laws for infinitary logic, Proc. 5th IEEE Symp. on Logic in Computer Science (1990), 156\u2013167. To appear in Information and Computation.","DOI":"10.1109\/LICS.1990.113742"},{"key":"7_CR20","unstructured":"Kolaitis, P., M.Y. Vardi, Fixpoint vs. infinitary logic in finite-model theory, to appear in Proc. 7th IEEE Symp. on Logic in Computer Science (1992)."},{"key":"7_CR21","unstructured":"Shemesh Y., N. Francez, Finite-state Datalog automata and relational languages, unpublished manuscript, 1988."},{"key":"7_CR22","unstructured":"Ullman, J.D., Principles of Database and Knowledge Base Systems, Computer Science Press, 1988."},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y., The complexity of relational query languages, Proc. 14th ACM Symp. on Theory of Computing (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2014 ICDT '92"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56039-4_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:46:08Z","timestamp":1742593568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56039-4_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540560395","9783540473602"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-56039-4_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}