{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T22:26:56Z","timestamp":1648679216118},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T00:00:00Z","timestamp":1278979200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Review of Symbolic Logic"],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>In this paper we consider an independence-friendly modal logic, IFML. It follows from results in the literature that qua expressive power, IFML is a fragment of second-order existential logic, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S1755020310000146_inline1\"><jats:alt-text>$\\Sigma _1^1$<\/jats:alt-text><\/jats:inline-graphic>, that cannot be translated into first-order logic. It is also known that IFML lacks the tree structure property. We show that IFML has the \u2018truncated structure property\u2019, a weaker version of the tree structure property, and that its satisfiability problem is solvable in 2NEXP. This implies that this paper reveals a new decidable fragment of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S1755020310000146_inline2\"><jats:alt-text>$\\Sigma _1^1$<\/jats:alt-text><\/jats:inline-graphic>. We also show that IFML becomes undecidable if we add the identity symbol to its vocabulary by means of a reduction from the tiling problem.<\/jats:p>","DOI":"10.1017\/s1755020310000146","type":"journal-article","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T08:25:13Z","timestamp":1279009513000},"page":"415-441","source":"Crossref","is-referenced-by-count":0,"title":["DECIDABILITY OF INDEPENDENCE-FRIENDLY MODAL LOGIC"],"prefix":"10.1017","volume":"3","author":[{"given":"MERLIJN","family":"SEVENSTER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,7,13]]},"reference":[{"key":"S1755020310000146_ref23","doi-asserted-by":"publisher","DOI":"10.2307\/2271440"},{"key":"S1755020310000146_ref21","volume-title":"The Convenience of Tiling","author":"van Emde Boas","year":"1996"},{"key":"S1755020310000146_ref18","first-page":"481","volume-title":"Advances in Modal Logic","volume":"6","author":"Tulenheimo","year":"2006"},{"key":"S1755020310000146_ref17","unstructured":"Tulenheimo T. (2004). Independence-friendly modal logic. PhD Thesis, University of Helsinki, Finland."},{"key":"S1755020310000146_ref16","unstructured":"Sevenster M. (2006). Branches of Imperfect Information: Logic, Games, and Computation. Ph. D. thesis, ILLC, Universiteit van Amsterdam."},{"key":"S1755020310000146_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01049180"},{"key":"S1755020310000146_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(00)00333-3"},{"key":"S1755020310000146_ref12","volume-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"S1755020310000146_ref11","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015542413718"},{"key":"S1755020310000146_ref22","first-page":"149","volume-title":"Descriptive Complexity and Finite Models, Volume 31 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Vardi","year":"1996"},{"key":"S1755020310000146_ref8","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/5.4.539"},{"key":"S1755020310000146_ref19","first-page":"237","volume-title":"New Perspectives on Games and Interaction","volume":"5","author":"V\u00e4\u00e4n\u00e4nen","year":"2008"},{"key":"S1755020310000146_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044481714-3\/50009-6"},{"key":"S1755020310000146_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511624919"},{"key":"S1755020310000146_ref5","first-page":"51","article-title":"Recurring dominoes: Making the highly undecidable highly understandable","volume":"24","author":"Harel","year":"1985","journal-title":"Annals of Discrete Mathematics"},{"key":"S1755020310000146_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107050884"},{"key":"S1755020310000146_ref1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004275029985"},{"key":"S1755020310000146_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-2464(07)80007-3"},{"key":"S1755020310000146_ref4","first-page":"1","volume-title":"Handbook of Modal Logic, Volume 3 of Studies in Logic and Practical Reasoning","author":"Blackburn","year":"2007"},{"key":"S1755020310000146_ref20","unstructured":"van Benthem J. F. A. K . (1976). Modal correspondence theory. PhD Thesis, Mathematisch Instituut & Instituut voor Grondlagenonderzoek, Universiteit van Amsterdam."},{"key":"S1755020310000146_ref15","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn102"},{"key":"S1755020310000146_ref10","first-page":"111","volume-title":"Advances in Modal Logic","volume":"5","author":"Hyttinen","year":"2005"},{"key":"S1755020310000146_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01049415"}],"container-title":["The Review of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1755020310000146","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T21:42:46Z","timestamp":1556401366000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1755020310000146\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,13]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["S1755020310000146"],"URL":"https:\/\/doi.org\/10.1017\/s1755020310000146","relation":{},"ISSN":["1755-0203","1755-0211"],"issn-type":[{"value":"1755-0203","type":"print"},{"value":"1755-0211","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,13]]}}}