{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:53:49Z","timestamp":1725900829024},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642360077"},{"type":"electronic","value":"9783642360084"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36008-4_8","type":"book-chapter","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T02:37:42Z","timestamp":1357094262000},"page":"174-197","source":"Crossref","is-referenced-by-count":1,"title":["Semantic Restrictions over Second-Order Logic"],"prefix":"10.1007","author":[{"given":"Flavio A.","family":"Ferrarotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro L.","family":"Grosso","sequence":"additional","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":"8_CR1","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"Abiteboul, S., Vianu, V.: Datalog extensions for database queries and updates. Journal of Computer and System Sciences\u00a043, 62\u2013124 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/256292.256295","volume":"44","author":"S. Abiteboul","year":"1997","unstructured":"Abiteboul, S., Vardi, M., Vianu, V.: Fixpoint logics, relational machines, and computational complexity. Journal of ACM\u00a044, 30\u201356 (1997)","journal-title":"Journal of ACM"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"292","DOI":"10.2307\/2272133","volume":"42","author":"J. Barwise","year":"1977","unstructured":"Barwise, J.: On Moschovakis closure ordinals. Journal of Symbolic Logic\u00a042, 292\u2013296 (1977)","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF02136173","volume":"18","author":"M. Cadoli","year":"1996","unstructured":"Cadoli, M., Schaerf, M.: On the complexity of Entailment in Propositional Multivalued Logics. Annals of Mathematics and Artificial Intelligence (AMAI)\u00a018, 29\u201350 (1996)","journal-title":"Annals of Mathematics and Artificial Intelligence (AMAI)"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"Cai, J., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"8_CR6","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. Information and Computation\u00a0143, 154\u2013174 (1998)","journal-title":"Information and Computation"},{"key":"8_CR7","unstructured":"Dawar, A.: Feasible Computation through Model Theory. Ph.D. thesis, University of Pennsylvania (1993)"},{"issue":"2","key":"8_CR8","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1093\/logcom\/8.2.189","volume":"8","author":"A. Durand","year":"1998","unstructured":"Durand, A., Lautemann, C., Schwentick, T.: Subclasses of Binary NP. Journal of Logic and Computation\u00a08(2), 189\u2013207 (1998)","journal-title":"Journal of Logic and Computation"},{"key":"8_CR9","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373 (1974)"},{"issue":"20","key":"8_CR10","first-page":"2934","volume":"16","author":"F.A. Ferrarotti","year":"2010","unstructured":"Ferrarotti, F.A., Paoletti, A.L., Turull-Torres, J.M.: Redundant Relations in Relational Databases: A Model Theoretic Perspective. Journal of Universal Computer Science\u00a016(20), 2934\u20132955 (2010)","journal-title":"Journal of Universal Computer Science"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-88594-8_3","volume-title":"Semantics in Data and Knowledge Bases","author":"F.A. Ferrarotti","year":"2008","unstructured":"Ferrarotti, F.A., Turull Torres, J.M.: The Relational Polynomial-Time Hierarchy and Second-Order Logic. In: Schewe, K.-D., Thalheim, B. (eds.) SDKB 2008. LNCS, vol.\u00a04925, pp. 48\u201376. Springer, Heidelberg (2008)"},{"key":"8_CR12","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. (1979) ISBN 0-7167-1045-5"},{"issue":"4","key":"8_CR13","doi-asserted-by":"publisher","first-page":"345","DOI":"10.2307\/420954","volume":"4","author":"M. Grohe","year":"1998","unstructured":"Grohe, M.: Finite variable logics in descriptive complexity theory. Bulletin of Symbolic Logic\u00a04(4), 345\u2013398 (1998)","journal-title":"Bulletin of Symbolic Logic"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Grosso, A.L., Turull-Torres, J.M.: A Second-Order Logic in which Variables Range over Relations with Complete First-Order Types. In: 2010 XXIX International Conference of the Chilean Computer Science Society, SCCC, pp. 270\u2013279. IEEE (2010)","DOI":"10.1109\/SCCC.2010.9"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-642-28279-9_10","volume-title":"Conceptual Modelling and Its Theoretical Foundations","author":"A.L. Grosso","year":"2012","unstructured":"Grosso, A.L., Turull-Torres, J.M.: SO\n                  F\n                : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy. In: D\u00fcsterh\u00f6ft, A., Klettke, M., Schewe, K.-D. (eds.) Conceptual Modelling and Its Theoretical Foundations. LNCS, vol.\u00a07260, pp. 116\u2013135. Springer, Heidelberg (2012)"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Gurevich, Y., Shela, S.: Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic\u00a032, 165\u2013180 (1986)","journal-title":"Annals of Pure and Applied Logic"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Gurevich, Y., Shela, S.: On finite rigid structures. Journal of Symbolic Logic 61 (1996)","DOI":"10.2307\/2275675"},{"key":"8_CR18","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 en polynomial time. Information and Control\u00a068, 86\u2013104 (1986)","journal-title":"Information and Control"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive and computational complexity. In: Hartmanis, J. (ed.) Computational Complexity Theory. Proc. of AMS Symposia in Appl. Math., vol.\u00a038, pp. 75\u201391 (1989)","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"8_CR20","unstructured":"Immerman, N.: Descriptive Complexity. Springer (1998) ISBN 0-387-98600-6"},{"issue":"2","key":"8_CR21","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P. Kolaitis","year":"1992","unstructured":"Kolaitis, P., Vardi, M.: Infinitary logics and 0-1 laws. Information and Commputation\u00a098(2), 258\u2013294 (1992)","journal-title":"Information and Commputation"},{"issue":"1","key":"8_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0168-0072(94)00025-X","volume":"74","author":"P. Kolaitis","year":"1995","unstructured":"Kolaitis, P., V\u00e4\u00e4n\u00e4nen, J.: Generalized quantifiers and pebble games on finite structures. Annals of Pure and Applied Logic\u00a074(1), 23\u201375 (1995)","journal-title":"Annals of Pure and Applied Logic"},{"key":"8_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BFb0022257","volume-title":"Computer Science Logic","author":"C. Lautemann","year":"1995","unstructured":"Lautemann, C., Schwentick, T., Th\u00e9rien, D.: Logics for Context-Free Languages. In: Pacholski, L., Tiuryn, J. (eds.) CSL 1994. LNCS, vol.\u00a0933, pp. 205\u2013216. Springer, Heidelberg (1995)"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer (2004) ISBN 3-5402-1202-7","DOI":"10.1007\/978-3-662-07003-1"},{"issue":"1","key":"8_CR25","doi-asserted-by":"publisher","first-page":"147","DOI":"10.2307\/2275602","volume":"61","author":"M. Otto","year":"1996","unstructured":"Otto, M.: The expressive power of fixed-point logic with counting. Journal of Symbolic Logic\u00a061(1), 147\u2013176 (1996)","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR26","doi-asserted-by":"crossref","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":"8_CR27","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley (1993) ISBN 0-2015-3082-1"},{"key":"8_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.: The polynomial-time hierarchy. Theoretical Computer Science\u00a03, 1\u201322 (1976)","journal-title":"Theoretical Computer Science"},{"key":"#cr-split#-8_CR29.1","doi-asserted-by":"crossref","unstructured":"Turull-Torres, J.M.: A study of homogeneity in relational databases. Annals of Mathematics and Artificial Intelligence 33(2-4), 379-414 (2001)","DOI":"10.1023\/A:1013132216581"},{"key":"#cr-split#-8_CR29.2","unstructured":"See also: Erratum for: A Study of Homogeneity in Relational Databases. Annals of Mathematics and Artificial Intelligence 33(2) 379-414 (2001), Annals of Mathematics and Artificial Intelligence 42, 443-444 (2004)"},{"issue":"3","key":"8_CR30","first-page":"485","volume":"17","author":"J.M. Turull-Torres","year":"2006","unstructured":"Turull-Torres, J.M.: Relational databases and homogeneity in logics with counting. Acta Cybernetica\u00a017(3), 485\u2013511 (2006)","journal-title":"Acta Cybernetica"},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Proc. 14th ACM Symposium on the Theory of Computing, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Semantics in Data and Knowledge Bases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36008-4_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:34:29Z","timestamp":1620135269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36008-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360077","9783642360084"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36008-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}