Skip navigation
Skip navigation

PSPACE bounds for rank-1 modal logics

Schroder, Lutz; Pattinson, Dirk

Description

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
URI: http://hdl.handle.net/1885/79810
Source: ACM Transactions on Computational Logic
DOI: 10.1145/1462179.1462185

Download

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:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator