Frame-validity Games and Lower Bounds on the Complexity of Modal Axioms

Logic Journal of the IGPL 30 (1):155-185 (2022)
  Copy   BIBTEX

Abstract

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,227

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

The modal logic of the countable random frame.Valentin Goranko & Bruce Kapron - 2003 - Archive for Mathematical Logic 42 (3):221-243.
Zero-one laws for modal logic.Jospeh Halpern & Bruce Kapron - 1994 - Annals of Pure and Applied Logic 69 (2-3):157-193.
Zero-one laws for modal logic.Joseph Y. Halpern & Bruce Kapron - 1994 - Annals of Pure and Applied Logic 69 (2-3):157-193.
Zero-one laws for modal logic (vol 69, pg 157, 1994).Joseph Y. Halpern & Bruce Kapron - 1994 - Annals of Pure and Applied Logic 69 (2-3):281-283.
Derivation rules as anti-axioms in modal logic.Yde Venema - 1993 - Journal of Symbolic Logic 58 (3):1003-1034.
A Modal Logic for Mixed Strategies.Joshua Sack & Wiebe van der Hoek - 2014 - Studia Logica 102 (2):339-360.
Some Exponential Lower Bounds on Formula-size in Modal Logic.Hans van Ditmarsch, Wiebe van der Hoek & Petar Iliev - 2014 - In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. CSLI Publications. pp. 139-157.
Lower Bounds for Modal Logics.Pavel Hrubeš - 2007 - Journal of Symbolic Logic 72 (3):941 - 958.
Elementary Canonical Formulae: A Survey on Syntactic, Algorithmic, and Modeltheoretic Aspects.W. Conradie, V. Goranko & D. Vakarelov - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 17-51.
Elementary Canonical Formulae: A Survey on Syntactic, Algorithmic, and Modeltheoretic Aspects.W. Conradie, V. Goranko & D. Vakarelov - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 17-51.
Modal sequents and definability.Bruce M. Kapron - 1987 - Journal of Symbolic Logic 52 (3):756-762.

Analytics

Added to PP
2020-12-19

Downloads
12 (#1,089,546)

6 months
6 (#529,161)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Andreas Herzig
Centre National de la Recherche Scientifique