{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T05:19:58Z","timestamp":1736313598753,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540317821"},{"type":"electronic","value":"9783540317845"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11663881_7","type":"book-chapter","created":{"date-parts":[[2006,1,19]],"date-time":"2006-01-19T11:31:46Z","timestamp":1137670306000},"page":"92-115","source":"Crossref","is-referenced-by-count":1,"title":["Arity and Alternation: A Proper Hierarchy in Higher Order Logics"],"prefix":"10.1007","author":[{"given":"Flavio A.","family":"Ferrarotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 M. Turull","family":"Torres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1994","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1994)"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: $\\Sigma^1_1$ -formulae on Finite Structures. Annals of Pure and Applied Logic\u00a024, 1\u201348 (1983)","journal-title":"Annals of Pure and Applied Logic"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, J.R.: Weak second-order arithmetic and finite automata. Z. Math. Logik und Grund. Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik und Grund. Math."},{"issue":"2","key":"7_CR4","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. Journal of Computer and System Sciences\u00a021(2), 156\u2013178 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR5","volume-title":"Finite Model Theory","author":"H. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"7_CR6","unstructured":"Ferrarotti, F.A., Turull Torres, J.M.: Arity and Alternation of Quantifiers in Higher Order Logics. To appear as a Technical Report of the Information Systems Department of Massey University (2005), http:\/\/infosys.massey.ac.nz\/research\/rs_techreports.html"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/BFb0049330","volume-title":"Computer Science Logic","author":"M. Grohe","year":"1994","unstructured":"Grohe, M.: Bounded Arity Hierarchies in Fixed-Point Logics. In: Meinke, K., B\u00f6rger, E., Gurevich, Y. (eds.) CSL 1993. LNCS, vol.\u00a0832, pp. 150\u2013164. Springer, Heidelberg (1994)"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0168-0072(95)00072-0","volume":"82","author":"M. Grohe","year":"1996","unstructured":"Grohe, M.: Arity Hierarchies. Annals of Pure and Applied Logic\u00a082, 103\u2013163 (1996)","journal-title":"Annals of Pure and Applied Logic"},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01268616","volume":"35","author":"M. Grohe","year":"1996","unstructured":"Grohe, M., Hella, L.: A Double Arity Hierarchy Theorem for Transitive Closure Logic. Archive for Mathematical Logic\u00a035, 157\u2013171 (1996)","journal-title":"Archive for Mathematical Logic"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(89)90070-5","volume":"43","author":"L. Hella","year":"1989","unstructured":"Hella, L.: Definability Hierarchies of Generalized Quantifiers. Annals of Pure and Applied Logic\u00a043, 235\u2013271 (1989)","journal-title":"Annals of Pure and Applied Logic"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Hella, L.: Logic Hierarchies in PTIME. In: Poceedings of the 7th IEEE Symposium in Logic and Computer Science, pp. 360\u2013368 (1992)","DOI":"10.1109\/LICS.1992.185548"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Hella, L., Turull-Torres, J.M.: Expressibility of Higher Order Logics. Electronic Notes in Theoretical Computer Science\u00a084 (2003)","DOI":"10.1016\/S1571-0661(04)80850-8"},{"key":"7_CR13","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Kolodziejczyk, L.A.: Truth Definitions in Finite Models. The Journal of Symbolic Logic\u00a069(1), 183\u2013200","DOI":"10.2178\/jsl\/1080938836"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Kolodziejczyk, L.A.: A Finite Model-Theoretical Proof of a Property of Bounded Query Classes within PH. The Journal of Symbolic Logic\u00a069(4), 1105\u20131116","DOI":"10.2178\/jsl\/1102022213"},{"key":"7_CR16","first-page":"228","volume-title":"Handbook of logic in artificial intelligence and logic programming","author":"D. Leivant","year":"1994","unstructured":"Leivant, D.: Higher order logic. In: Gabbay, D.M., et al. (eds.) Handbook of logic in artificial intelligence and logic programming, vol.\u00a02, pp. 228\u2013321. Oxford University Press, Oxford (1994)"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0168-0072(95)00013-5","volume":"78","author":"J.A. Makowsky","year":"1996","unstructured":"Makowsky, J.A., Pnueli, Y.B.: Arity and alternation in second-order logic. Annals of Pure and Applied Logics\u00a078, 189\u2013202 (1996)","journal-title":"Annals of Pure and Applied Logics"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/BFb0055826","volume-title":"Mathematical Foundations of Computer Science 1998","author":"O. Matz","year":"1998","unstructured":"Matz, O.: One Existential Quantifier will do in Existential Monadic Second-Order Logic Over Pictures. In: Brim, L., Gruska, J., Zlatu\u0161ka, J. (eds.) MFCS 1998. LNCS, vol.\u00a01450, pp. 751\u2013759. Springer, Heidelberg (1998)"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/inco.2002.2955","volume":"179","author":"O. Matz","year":"2002","unstructured":"Matz, O., Schweikardt, N., Thomas, W.: The Monadic Quantifier Alternation Hierarchy over Grids and Graphs. Information and Computation\u00a0179, 356\u2013383 (2002)","journal-title":"Information and Computation"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1002\/1521-3870(200111)47:4<513::AID-MALQ513>3.0.CO;2-J","volume":"47","author":"M. Mostowski","year":"2001","unstructured":"Mostowski, M.: On Representing Concepts in Finite Models. Mathematical Logic Quarterly\u00a047, 513\u2013523 (2001)","journal-title":"Mathematical Logic Quarterly"},{"key":"7_CR21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-94-017-2612-2_2","volume-title":"Philosophical Dimensions of Logic and Science: Selected Contributed Papers from the 11th International Congress of Logic, Methodology, and Philosophy of Science, Krakow","author":"M. Mostowski","year":"2003","unstructured":"Mostowski, M.: On Representing Semantics in Finite Models. In: Rojszczak, A., Cachro, J., Kurczewski, G. (eds.) Philosophical Dimensions of Logic and Science: Selected Contributed Papers from the 11th International Congress of Logic, Methodology, and Philosophy of Science, Krakow, pp. 15\u201328. Kluwer, Dordrecht (2003)"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0020-0190(94)00219-O","volume":"53","author":"M. Otto","year":"1995","unstructured":"Otto, M.: Note on the Number of Monadic Quantifiers in Monadic $\\Sigma^1_1$ . Inform. Process. Lett.\u00a053, 337\u2013339 (1995)","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"7_CR23","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), 1\u201322 (1976)","journal-title":"Theoretical Computer Science"},{"key":"7_CR24","series-title":"Logic, Semantics, Metamathematics","first-page":"152","volume-title":"Warszawa, Nak\u0142adem Towarzystwa Naukowego Warszawskiego (1933); English translation of the German version: The Concept of Truth in Formalized Languages","author":"A. Tarski","year":"1956","unstructured":"Tarski, A.: Poje\u0327cie prawdy w je\u0327zykach nauk dedukcyjnych. In: Tarsky, A. (ed.) Warszawa, Nak\u0142adem Towarzystwa Naukowego Warszawskiego (1933); English translation of the German version: The Concept of Truth in Formalized Languages. Logic, Semantics, Metamathematics, pp. 152\u2013278. Clarendon Press, Oxford (1956)"},{"key":"7_CR25","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"Thomas, W.: Classifying Regular Events in Symbolic Logic. J. Comput, System Sci.\u00a025, 360\u2013376 (1982)","journal-title":"J. Comput, System Sci."},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Vardi, M.: The Complexity of Relational Query Languages. In: Proceedings of the 14th ACM Symposium on Theory of Computing, pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Foundations of Information and Knowledge Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11663881_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T06:55:12Z","timestamp":1736232912000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11663881_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540317821","9783540317845"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11663881_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}