{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T14:29:28Z","timestamp":1648736968658},"reference-count":27,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T00:00:00Z","timestamp":1623801600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Helsinki including Helsinki University Central Hospital"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We analyze the expressive resources of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {IF}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>IF<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula> logic that do not stem from Henkin (partially-ordered) quantification. When one restricts attention to regular <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {IF}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>IF<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula> sentences, this amounts to the study of the fragment of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {IF}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>IF<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula> logic which is individuated by the game-theoretical property of action recall (AR). We prove that the fragment of prenex AR sentences can express all existential second-order properties. We then show that the same can be achieved in the non-prenex fragment of AR, by using \u201csignalling by disjunction\u201d instead of Henkin or signalling patterns. We also study irregular IF logic (in which requantification of variables is allowed) and analyze its correspondence to regular IF logic. By using new methods, we prove that the game-theoretical property of knowledge memory is a first-order syntactical constraint also for irregular sentences, and we identify another new first-order fragment. Finally we discover that irregular prefixes behave quite differently in finite and infinite models. In particular, we show that, over infinite structures, every irregular prefix is equivalent to a regular one; and we present an irregular prefix which is second order on finite models but collapses to a first-order prefix on infinite models.<\/jats:p>","DOI":"10.1007\/s00153-021-00781-8","type":"journal-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T07:02:38Z","timestamp":1623826958000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Independence-friendly logic without Henkin quantification"],"prefix":"10.1007","author":[{"given":"Fausto","family":"Barbero","sequence":"first","affiliation":[]},{"given":"Lauri","family":"Hella","sequence":"additional","affiliation":[]},{"given":"Raine","family":"R\u00f6nnholm","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,16]]},"reference":[{"key":"781_CR1","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1017\/S175502031200038X","volume":"6","author":"F Barbero","year":"2013","unstructured":"Barbero, F.: On existential declarations of independence in IF logic. Rev. Symb. Log. 6, 254\u2013280 (2013)","journal-title":"Rev. Symb. Log."},{"issue":"1","key":"781_CR2","doi-asserted-by":"publisher","first-page":"102859","DOI":"10.1016\/j.apal.2020.102859","volume":"172","author":"F Barbero","year":"2021","unstructured":"Barbero, F.: Complexity of syntactical tree fragments of independence-friendly logic. Ann. Pure Appl. Log. 172(1), 102859 (2021)","journal-title":"Ann. Pure Appl. Log."},{"key":"781_CR3","doi-asserted-by":"crossref","unstructured":"Barbero, F., Hella, L., R\u00f6nnholm, R.: Independence-friendly logic without Henkin quantification. In: Kennedy, J., de\u00a0Queiroz, R. (eds.) International Workshop on Logic, Language, Information, and Computation, pp. 14\u201330. Springer (2017)","DOI":"10.1007\/978-3-662-55386-2_2"},{"key":"781_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1093\/jigpal\/jzn030","volume":"17","author":"X Caicedo","year":"2009","unstructured":"Caicedo, X., Dechesne, F., Janssen, T.M.V.: Equivalence and quantifier rules for logic with imperfect information. Log. J. IGPL 17, 91\u2013129 (2009)","journal-title":"Log. J. IGPL"},{"key":"781_CR5","doi-asserted-by":"crossref","unstructured":"Caicedo, X., Krynicki, M.: Quantifiers for reasoning with imperfect information and $$\\Sigma _1^1$$-logic. In: I.M.L.O., Carnielli, W.A. (eds.) Contemporary Mathematics, vol. 235, pp. 17\u201331. American Mathematical Society, Providence (1999)","DOI":"10.1090\/conm\/235\/03463"},{"key":"781_CR6","doi-asserted-by":"publisher","first-page":"673","DOI":"10.2307\/2695036","volume":"66","author":"P Cameron","year":"2001","unstructured":"Cameron, P., Hodges, W.: Some combinatorics of imperfect information. J. Symb. Log. 66, 673\u2013684 (2001)","journal-title":"J. Symb. Log."},{"key":"781_CR7","doi-asserted-by":"crossref","unstructured":"Dahlhaus, E.: Reduction to NP-complete problems by interpretations. In: Proceedings of the Symposium \u201cRekursive Kombinatorik\u201d on Logic and Machines: Decision Problems and Complexity, pp. 357\u2013365 (1983)","DOI":"10.1007\/3-540-13331-3_51"},{"key":"781_CR8","unstructured":"Dechesne, F.: Game, set, maths: formal investigations into logic with imperfect information. Ph.D. thesis, Tilburg University, Tilburg (2005)"},{"issue":"8","key":"781_CR9","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1002\/malq.19700160802","volume":"16","author":"HB Enderton","year":"1970","unstructured":"Enderton, H.B.: Finite partially ordered quantifiers. Math. Log. Q. 16(8), 393\u2013397 (1970)","journal-title":"Math. Log. Q."},{"key":"781_CR10","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (eds.)Complexity of Computation, SIAM-AMS Proceedings, vol. 7, pp. 27\u201341 (1974)"},{"key":"781_CR11","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(90)90009-A","volume":"40","author":"E Grandjean","year":"1990","unstructured":"Grandjean, E.: First-order spectra with one variable. J. Comput. Syst. Sci. 40, 136\u2013153 (1990)","journal-title":"J. Comput. Syst. Sci."},{"key":"781_CR12","unstructured":"Henkin, L.: Some remarks on infinitely long formulas. In: Bernays. P. (ed.) Infinitistic Methods, pp. 167\u2013183. Pergamon Press, London (1961)"},{"key":"781_CR13","first-page":"571","volume-title":"Logic, Methodology and Philosophy of Science VIII","author":"J Hintikka","year":"1989","unstructured":"Hintikka, J., Sandu, G.: Informational independence as a semantical phenomenon. In: Fenstad, J.E., et al. (eds.) Logic, Methodology and Philosophy of Science VIII, pp. 571\u2013589. Elsevier, Amsterdam (1989)"},{"key":"781_CR14","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1093\/jigpal\/5.4.539","volume":"5","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: Compositional semantics for a language of imperfect information. Log. J. IGPL 5, 539\u2013563 (1997)","journal-title":"Log. J. IGPL"},{"key":"781_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/3-540-63246-8_4","volume-title":"Structures in Logic and Computer Science","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: Some strange quantifiers. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. Lecture Notes in Computer Science, vol. 1261, pp. 51\u201365. Springer, London (1997)"},{"key":"781_CR16","first-page":"111","volume":"5","author":"T Hyttinen","year":"2005","unstructured":"Hyttinen, T., Tulenheimo, T.: Decidability of IF modal logic of perfect recall. Adv. Modal Log. 5, 111\u2013131 (2005)","journal-title":"Adv. Modal Log."},{"key":"781_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity. Graduate Texts in Computer Science","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, New York (1999)"},{"key":"781_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1023\/A:1015542413718","volume":"11","author":"TMV Janssen","year":"2002","unstructured":"Janssen, T.M.V.: Independent choices and the interpretation of IF logic. J. Log. Lang. Inf. 11, 367\u2013387 (2002)","journal-title":"J. Log. Lang. Inf."},{"key":"781_CR19","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-1-4020-5012-7_15","volume-title":"The Age of Alternative Logics","author":"TMV Janssen","year":"2006","unstructured":"Janssen, T.M.V., Dechesne, F.: Signalling in IF games: a tricky business. In: Van Benthem, J., Heinzmann, G., Rebuschi, M., Visser, H. (eds.) The Age of Alternative Logics, pp. 221\u2013241. Springer, New York (2006)"},{"key":"781_CR20","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1002\/malq.19930390134","volume":"39","author":"M Krynicki","year":"1993","unstructured":"Krynicki, M.: Hierarchies of partially ordered connectives and quantifiers. Math. Log. Q. 39, 287\u2013294 (1993)","journal-title":"Math. Log. Q."},{"key":"781_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series","author":"L Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, New York (2004). https:\/\/doi.org\/10.1007\/978-3-662-07003-1"},{"key":"781_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511981418","volume-title":"Independence-Friendly Logic\u2014A Game-Theoretic Approach, London Mathematical Society Lecture Note Series","author":"AL Mann","year":"2011","unstructured":"Mann, A.L., Sandu, G., Sevenster, M.: Independence-Friendly Logic\u2014A Game-Theoretic Approach, London Mathematical Society Lecture Note Series, vol. 386. Cambridge University Press, Cambridge (2011)"},{"key":"781_CR23","doi-asserted-by":"crossref","unstructured":"Mostowski, M.: The relational semantics for branched quantifiers. In: Skordev, D.G. (ed.) Mathematical Logic and Its Applications, pp. 315\u2013322. Springer, New York (1987)","DOI":"10.1007\/978-1-4613-0897-3_23"},{"key":"781_CR24","unstructured":"Sevenster, M.: Branches of imperfect information: logic, games, and computation. Ph.D. thesis, ILLC, Universiteit van Amsterdam (2006)"},{"issue":"04","key":"781_CR25","doi-asserted-by":"publisher","first-page":"1224","DOI":"10.1017\/jsl.2013.30","volume":"79","author":"M Sevenster","year":"2014","unstructured":"Sevenster, M.: Dichotomy result for independence-friendly prefixes of generalized quantifiers. J. Symb. Log. 79(04), 1224\u20131246 (2014)","journal-title":"J. Symb. Log."},{"key":"781_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511611193","volume-title":"Dependence Logic: A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts","author":"J V\u00e4\u00e4n\u00e4nen","year":"2007","unstructured":"V\u00e4\u00e4n\u00e4nen, J.: Dependence Logic: A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts, vol. 70. Cambridge University Press, Cambridge (2007)"},{"key":"781_CR27","unstructured":"Virtema, J.: Approaches to finite variable dependence: expressiveness and computational complexity. Ph.D. thesis, University of Tampere (2014)"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-021-00781-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-021-00781-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-021-00781-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T07:03:02Z","timestamp":1623826982000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-021-00781-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,16]]},"references-count":27,"alternative-id":["781"],"URL":"https:\/\/doi.org\/10.1007\/s00153-021-00781-8","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,16]]},"assertion":[{"value":"1 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}