{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T15:10:34Z","timestamp":1737299434399,"version":"3.33.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2007,7,18]],"date-time":"2007-07-18T00:00:00Z","timestamp":1184716800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2007,7,31]]},"DOI":"10.1007\/s10472-007-9071-4","type":"journal-article","created":{"date-parts":[[2007,7,17]],"date-time":"2007-07-17T07:31:01Z","timestamp":1184657461000},"page":"111-141","source":"Crossref","is-referenced-by-count":1,"title":["Arity and alternation: a proper hierarchy in higher order logics"],"prefix":"10.1007","volume":"50","author":[{"given":"Flavio Antonio","family":"Ferrarotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 Mar\u00eda","family":"Turull Torres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,18]]},"reference":[{"key":"9071_CR1","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1994","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Redwood City, CA (1994)"},{"key":"9071_CR2","doi-asserted-by":"crossref","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. Ann. Pure Appl. Logic 24, 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9071_CR3","doi-asserted-by":"crossref","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. Log. Grundl. Math. 6, 66\u201392 (1960)","journal-title":"Z. Math. Log. Grundl. Math."},{"issue":"2","key":"9071_CR4","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., Harel, D.: Computable queries for relational data bases. J. Comput. Syst. Sci. 21(2), 156\u2013178 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"9071_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-28788-4","volume-title":"Finite model theory","author":"H. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H., Flum, J.: Finite model theory, 2nd edn. Springer, Berlin Heidelberg New York (1999)","edition":"2"},{"key":"9071_CR6","first-page":"89","volume":"21","author":"C.C. Elgot","year":"1961","unstructured":"Elgot, C.C.: Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc. 21, 89\u201396 (1961)","journal-title":"Trans. Am. Math. Soc."},{"key":"9071_CR7","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","volume":"21","author":"R. Fagin","year":"1975","unstructured":"Fagin, R.: A spectrum hierarchy. Z. Math. Log. Grundl. Math. 21, 123\u2013134 (1975)","journal-title":"Z. Math. Log. Grundl. Math."},{"unstructured":"Ferrarotti, F.A., Turull Torres, J.M.: Arity and alternation of quantifiers in higher order logics. Technical report number 10\/2005. Department of Information Systems, Massey University, New Zealand (2005) http:\/\/infosys.massey.ac.nz\/research\/rs_techreports.html","key":"9071_CR8"},{"key":"9071_CR9","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/11663881_7","volume":"3861","author":"F.A. Ferrarotti","year":"2006","unstructured":"Ferrarotti, F.A., Turull Torres, J.M.: Arity and alternation: a proper hierarchy in higher order logics. Lect. Notes Comput. Sci. 3861, 92\u2013115 (2006)","journal-title":"Lect. Notes Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Grohe, M.: Bounded arity hierarchies in fixed-point logics. In: Proceedings of the 7th Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol. 832, pp. 150\u2013164 (1993)","key":"9071_CR10","DOI":"10.1007\/BFb0049330"},{"key":"9071_CR11","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0168-0072(95)00072-0","volume":"82","author":"M. Grohe","year":"1996","unstructured":"Grohe, M.: Arity hierarchies. Ann. Pure Appl. Logic 82, 103\u2013163 (1996)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9071_CR12","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. Arch. Math. Log. 35, 157\u2013171 (1996)","journal-title":"Arch. Math. Log."},{"key":"9071_CR13","doi-asserted-by":"crossref","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. Ann. Pure Appl. Logic 43, 235\u2013271 (1989)","journal-title":"Ann. Pure Appl. Logic"},{"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)","key":"9071_CR14","DOI":"10.1109\/LICS.1992.185548"},{"doi-asserted-by":"crossref","unstructured":"Hella, L., Turull Torres, J.M.: Expressibility of higher order logics. Electr. Notes Theor. Comput. Sci. 84 (2003)","key":"9071_CR15","DOI":"10.1016\/S1571-0661(04)80850-8"},{"key":"9071_CR16","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.tcs.2006.01.009","volume":"355","author":"L. Hella","year":"2006","unstructured":"Hella, L., Turull Torres, J.M.: Computing queries with higher order logics. Theor. Comput. Sci. 355, 197\u2013214 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9071_CR17","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, Redwood City, CA (1979)"},{"key":"9071_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive complexity. Springer, Berlin Heidelberg New York (1999)"},{"issue":"1","key":"9071_CR19","doi-asserted-by":"crossref","first-page":"183","DOI":"10.2178\/jsl\/1080938836","volume":"69","author":"L.A. Kolodziejczyk","year":"2004","unstructured":"Kolodziejczyk, L.A.: Truth definitions in finite models. J. Symb. Log. 69(1), 183\u2013200 (2004)","journal-title":"J. Symb. Log."},{"issue":"4","key":"9071_CR20","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.2178\/jsl\/1102022213","volume":"69","author":"L.A. Kolodziejczyk","year":"2004","unstructured":"Kolodziejczyk, L.A.: A finite model-theoretical proof of a property of bounded query classes within PH. The J. Symb. Log. 69(4), 1105\u20131116 (2004)","journal-title":"The J. Symb. Log."},{"unstructured":"Kolodziejczyk, L.A.: Truth definitions and higher order logics in finite models. Ph.D. thesis, Warsaw University, Warsaw, Poland (2005)","key":"9071_CR21"},{"key":"9071_CR22","first-page":"228","volume-title":"Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 2","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. 2, pp. 228\u2013321. Oxford University Press, Oxford (1994)"},{"key":"9071_CR23","doi-asserted-by":"crossref","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. Springer, Berlin Heidelberg New York (2004)"},{"key":"9071_CR24","doi-asserted-by":"crossref","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. Ann. Pure Appl. Logic 78, 189\u2013202 (1996)","journal-title":"Ann. Pure Appl. Logic"},{"doi-asserted-by":"crossref","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.) Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 1450, pp. 751\u2013759 (1998)","key":"9071_CR25","DOI":"10.1007\/BFb0055826"},{"key":"9071_CR26","doi-asserted-by":"crossref","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. Inf. Comput. 179, 356\u2013383 (2002)","journal-title":"Inf. Comput."},{"key":"9071_CR27","doi-asserted-by":"crossref","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. Math. Log. Q. 47, 513\u2013523 (2001)","journal-title":"Math. Log. Q."},{"doi-asserted-by":"crossref","unstructured":"Mostowski, M.: On representing semantics in finite models. In: Rojszczak, A., Cachro, J., Kurczewski, G. (eds.) Philosophical Dimensions of Logic and Science, 11th International Congress of Logic, Methodology, and Philosophy of Science, Krakow, 1999, pp. 15\u201328, 1999. Kluwer, Deventer (2003)","key":"9071_CR28","DOI":"10.1007\/978-94-017-2612-2_2"},{"key":"9071_CR29","doi-asserted-by":"crossref","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$ . Inf. Process. Lett. 53, 337\u2013339 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9071_CR30","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Tarski, A.: Poj\u0327cie prawdy w je\u0327zykach nauk dedukcyjnych. Warszawa, Nak\u0142adem Towarzystwa Naukowego Warszawskiego (1933) English translation of the German version: The concept of truth in formalized languages. Logic, semantics, metamathematics. Clarendon Press, Oxford, pp. 152\u2013278 (1956)","key":"9071_CR31"},{"key":"9071_CR32","doi-asserted-by":"crossref","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, Syst. Sci. 25, 360\u2013376 (1982)","journal-title":"J. Comput, Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Vardi, M.: The complexity of relational query languages. In: Proceedings of the 14th ACM Symposium on Theory of Computing, San Francisco, CA, USA, pp. 137\u2013146 (1982)","key":"9071_CR33","DOI":"10.1145\/800070.802186"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-007-9071-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-007-9071-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-007-9071-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T14:49:54Z","timestamp":1737298194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-007-9071-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,18]]},"references-count":33,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2007,7,31]]}},"alternative-id":["9071"],"URL":"https:\/\/doi.org\/10.1007\/s10472-007-9071-4","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2007,7,18]]}}}