Some Exponential Lower Bounds on Formula-size in Modal Logic

, &
In Rajeev Goré, Barteld Kooi & Agi Kurucz (eds.), Advances in Modal Logic, Volume 10. CSLI Publications. pp. 139-157 (2014)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Add categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

External links

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

Through your library

My notes

Similar books and articles

Lower Bounds for Modal Logics.Pavel Hrubeš - 2007 - Journal of Symbolic Logic 72 (3):941 - 958.
Sharpened lower bounds for cut elimination.Samuel R. Buss - 2012 - Journal of Symbolic Logic 77 (2):656-668.
On lengths of proofs in non-classical logics.Pavel Hrubeš - 2009 - Annals of Pure and Applied Logic 157 (2-3):194-205.
Separation results for the size of constant-depth propositional proofs.Arnold Beckmann & Samuel R. Buss - 2005 - Annals of Pure and Applied Logic 136 (1-2):30-55.
Proof complexity of propositional default logic.Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas & Heribert Vollmer - 2011 - Archive for Mathematical Logic 50 (7-8):727-742.
The complexity of first-order and monadic second-order logic revisited.Markus Frick & Martin Grohe - 2004 - Annals of Pure and Applied Logic 130 (1-3):3-31.
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Lower Bounds for cutting planes proofs with small coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
On the complexity of proof deskolemization.Matthias Baaz, Stefan Hetzl & Daniel Weller - 2012 - Journal of Symbolic Logic 77 (2):669-686.
Reachability logic: an efficient fragment of transitive closure logic.N. Alechina & N. Immerman - 2000 - Logic Journal of the IGPL 8 (3):325-337.
The succinctness of first-order logic over modal logic via a formula size game.Lauri Hella & Miikka Vilander - 2016 - In Lev Beklemishev, Stéphane Demri & András Máté (eds.), Advances in Modal Logic, Volume 11. CSLI Publications. pp. 491-419.
A lower bound for intuitionistic logic.Pavel Hrubeš - 2007 - Annals of Pure and Applied Logic 146 (1):72-90.
Lower Bounds for Cutting Planes Proofs with Small Coefficients.Maria Bonet, Toniann Pitassi & Ran Raz - 1997 - Journal of Symbolic Logic 62 (3):708-728.
Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations.Pavel Pudlak - 1997 - Journal of Symbolic Logic 62 (3):981-998.

Analytics

Added to PP
2018-02-24

Downloads
19 (#753,814)

6 months
5 (#544,079)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

The succinctness of the cover modality.H. Van Ditmarsch & P. Iliev - 2015 - Journal of Applied Non-Classical Logics 25 (4):373-405.
The succinctness of first-order logic over modal logic via a formula size game.Lauri Hella & Miikka Vilander - 2016 - In Lev Beklemishev, Stéphane Demri & András Máté (eds.), Advances in Modal Logic, Volume 11. CSLI Publications. pp. 491-419.

Add more citations

References found in this work

Modal Logic.Patrick Blackburn, Maarten de Rijke & Yde Venema - 2001 - Studia Logica 76 (1):142-148.
Modal logic and classical logic.Johan van Benthem - 1983 - Atlantic Highlands, N.J.: Distributed in the U.S.A. by Humanities Press.
Modal Logic and Classical Logic.R. A. Bull - 1987 - Journal of Symbolic Logic 52 (2):557-558.

View all 7 references / Add more references