Skip navigation
Skip navigation

PSPACE bounds for rank-1 modal logics

Schroder, Lutz; Pattinson, Dirk


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]

CollectionsANU Research Publications
Date published: 2009
Type: Journal article
Source: ACM Transactions on Computational Logic
DOI: 10.1145/1462179.1462185


File Description SizeFormat Image
01_Schroder_PSPACE_bounds_for_rank-1_modal_2009.pdf252.34 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator