{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T01:27:18Z","timestamp":1700443638580},"reference-count":27,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T00:00:00Z","timestamp":1608163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We introduce frame-equivalence games tailored for reasoning about the size, modal depth, number of occurrences of symbols and number of different propositional variables of modal formulae defining a given frame property. Using these games, we prove lower bounds on the above measures for a number of well-known modal axioms; what is more, for some of the axioms, we show that they are optimal among the formulae defining the respective class of frames.<\/jats:p>","DOI":"10.1093\/jigpal\/jzaa068","type":"journal-article","created":{"date-parts":[[2020,11,15]],"date-time":"2020-11-15T20:07:10Z","timestamp":1605470830000},"page":"155-185","source":"Crossref","is-referenced-by-count":2,"title":["Frame-validity Games and Lower Bounds on the Complexity of Modal Axioms"],"prefix":"10.1093","volume":"30","author":[{"given":"Philippe","family":"Balbiani","sequence":"first","affiliation":[{"name":"IRIT, CNRS Toulouse University, F-31062 Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Fern\u00e1ndez-Duque","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Ghent University Department of Mathematics, Ghent University, B 9000 Gent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Herzig","sequence":"additional","affiliation":[{"name":"IRIT, CNRS Toulouse University, F-31062 Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petar","family":"Iliev","sequence":"additional","affiliation":[{"name":"Institute of Philosophy and Sociology, Bulgarian Academy of Sciences, Sofia 1000, Bulgaria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,12,17]]},"reference":[{"key":"2022011721343205000_ref1","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1145\/772062.772064","article-title":"An $\\mathrm{n}!$ lower bound on formula size","volume":"4","author":"Adler","year":"2003","journal-title":"ACM Transactions on Computational Logic"},{"key":"2022011721343205000_ref2","first-page":"83","article-title":"Frame validity games and absolute minimality of modal axioms","volume-title":"Proceedings of Advances in Modal Logic","author":"Balbiani","year":"2018"},{"key":"2022011721343205000_ref3","first-page":"29","article-title":"Modal logics for region-based theories of space","volume":"81","author":"Balbiani","year":"2007","journal-title":"Fundamenta Informaticae"},{"key":"2022011721343205000_ref4","article-title":"Oxford Logic Guides","volume-title":"Modal Logic","author":"Chagrov","year":"1997"},{"key":"2022011721343205000_ref5","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1080\/11663081.2016.1144016","article-title":"The succinctness of the cover modality","volume":"25","author":"van Ditmarsch","year":"2015","journal-title":"Journal of Applied Non-classical Logics"},{"key":"2022011721343205000_ref6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","article-title":"An application of games to the completeness problem for formalized theories","volume":"49","author":"Ehrenfeucht","year":"1961","journal-title":"Fundamenta Mathematicae"},{"key":"2022011721343205000_ref7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","article-title":"Finite model theory\u2014A personal perspective","volume":"116","author":"Fagin","year":"1993","journal-title":"Theoretical Computer Science"},{"key":"2022011721343205000_ref8","first-page":"827","article-title":"Succinctness in subsystems of the spatial $\\mu $-calculus","volume":"5","author":"Fern\u00e1ndez-Duque","year":"2018","journal-title":"Journal of Applied Logics"},{"key":"2022011721343205000_ref9","first-page":"114","article-title":"On the size of shortest modal descriptions","volume-title":"Proceedings of Advances in Modal Logic","author":"Figueira","year":"2010"},{"key":"2022011721343205000_ref10","volume-title":"Finite Model Theory","author":"Ebbinghaus","year":"1995"},{"key":"2022011721343205000_ref11","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.artint.2013.02.003","article-title":"On the succinctness of some modal logics","volume":"197","author":"French","year":"2013","journal-title":"Artificial Intelligence"},{"key":"2022011721343205000_ref12","first-page":"881","article-title":"Succinctness of epistemic languages","volume-title":"Proceedings of IJCAI","author":"French","year":"2011"},{"key":"2022011721343205000_ref13","first-page":"77","article-title":"On canonical modal logics that are not elementarily determined","volume":"46","author":"Goldblatt","year":"2003","journal-title":"Logique et Analyse Nouvelle S\u00e9rie"},{"key":"2022011721343205000_ref14","first-page":"401","article-title":"The succinctness of first-order logic over modal logic via a formula size game","volume-title":"Proceedings of Advances in Modal Logic","author":"Hella","year":"2016"},{"key":"2022011721343205000_ref15","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1093\/logcom\/exz025","article-title":"Formula size games for modal logic and $\\mu $-calculus","volume":"29","author":"Hella","year":"2019","journal-title":"Journal of Logic and Computation"},{"key":"2022011721343205000_ref16","first-page":"341","article-title":"On the relative succinctness of modal logics with union, intersection and quantification","volume-title":"Proceedings of AAMAS","author":"van der Hoek","year":"2014"},{"key":"2022011721343205000_ref17","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF00935597","article-title":"Every world can see a reflexive world","volume":"49","author":"Hughes","year":"1990","journal-title":"Studia Logica"},{"key":"2022011721343205000_ref18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/038\/1020810","article-title":"Descriptive and computational complexity","volume-title":"Computational Complexity Theory","author":"Immerman","year":"1989"},{"key":"2022011721343205000_ref19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"Immerman","year":"1999"},{"key":"2022011721343205000_ref20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity: Advances and Frontiers","author":"Jukna","year":"2012"},{"key":"2022011721343205000_ref21","first-page":"539","article-title":"Monotone circuits for connectivity require super-logarithmic depth","volume-title":"Proceedings of the 20th ACM STOC","author":"Karchmer","year":"1988"},{"key":"2022011721343205000_ref22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"Libkin","year":"2004"},{"key":"2022011721343205000_ref23","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/1160633.1160657","article-title":"Complexity and succinctness of public announcement logic","volume-title":"Proceedings of AAMAS","author":"Lutz","year":"2006"},{"key":"2022011721343205000_ref24","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1090\/conm\/558\/11050","article-title":"Logical complexity of graphs: A survey","volume-title":"Model Theoretic Methods in Finite Combinatorics","author":"Pikhurko","year":"2011"},{"key":"2022011721343205000_ref25","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02122698","article-title":"Applications of matrix methods to the theory of lower bounds in computational complexity","volume":"10","author":"Razborov","year":"1990","journal-title":"Combinatorica"},{"key":"2022011721343205000_ref26","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(84)90166-3","article-title":"On the definability of properties of finite graphs","volume":"49","author":"Tur\u00e1n","year":"1984","journal-title":"Discrete Mathematics"},{"key":"2022011721343205000_ref27","first-page":"499","article-title":"Modal definability in languages with a finite number of propositional variables and a new extension of the Sahlqvist\u2019s class","volume-title":"Proceedings of Advances in Modal Logic","author":"Vakarelov","year":"2003"}],"container-title":["Logic Journal of the IGPL"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/30\/1\/155\/42198243\/jzaa068.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/30\/1\/155\/42198243\/jzaa068.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T21:35:00Z","timestamp":1642455300000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jigpal\/article\/30\/1\/155\/6039977"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,17]]},"references-count":27,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,12,17]]},"published-print":{"date-parts":[[2022,1,11]]}},"URL":"https:\/\/doi.org\/10.1093\/jigpal\/jzaa068","relation":{},"ISSN":["1367-0751","1368-9894"],"issn-type":[{"value":"1367-0751","type":"print"},{"value":"1368-9894","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,2]]},"published":{"date-parts":[[2020,12,17]]}}}