PSPACE bounds for rank-1 modal logics
For lack of general algorithmic methods that apply to wide classes of logics, establishing a complexity bound for a given modal logic is often a laborious task. The present work is a step towards a general theory of the complexity of modal logics. Our main result is that all rank-1 logics enjoy a shallow model property and thus are, under mild assumptions on the format of their axiomatisation, in PSPACE. This leads to a unified derivation of tight PSPACE-bounds for a number of logics, including...[Show more]
|Collections||ANU Research Publications|
|Source:||ACM Transactions on Computational Logic|
|01_Schroder_PSPACE_bounds_for_rank-1_modal_2009.pdf||252.34 kB||Adobe PDF||Request a copy|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.