Skip navigation
Skip navigation

Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra

Schroder, Lutz; Pattinson, Dirk

Description

State-based systems and modal logics for reasoning about them often heterogeneously combine a number of features such as non-determinism and probabilities. In this paper, we show that the combination of features can be reflected algorithmically, and we develop modular decision procedures for heterogeneous modal logics. The modularity is achieved by formalising the underlying state-based systems as multi-sorted coalgebras and associating both a logical and algorithmic description with a number...[Show more]

dc.contributor.authorSchroder, Lutz
dc.contributor.authorPattinson, Dirk
dc.date.accessioned2015-12-13T22:42:39Z
dc.identifier.issn0960-1295
dc.identifier.urihttp://hdl.handle.net/1885/78863
dc.description.abstractState-based systems and modal logics for reasoning about them often heterogeneously combine a number of features such as non-determinism and probabilities. In this paper, we show that the combination of features can be reflected algorithmically, and we develop modular decision procedures for heterogeneous modal logics. The modularity is achieved by formalising the underlying state-based systems as multi-sorted coalgebras and associating both a logical and algorithmic description with a number of basic building blocks. Our main result is that logics arising as combinations of these building blocks can be decided in polynomial space provided this is also the case for the components. By instantiating the general framework to concrete cases, we obtain PSpace decision procedures for a wide variety of structurally different logics, describing, for example, Segala systems and games with uncertain information.
dc.publisherCambridge University Press
dc.sourceMathematical Structures in Computer Science
dc.subjectKeywords: Basic building block; Building blockes; Coalgebras; Decision procedure; Modal logic; Modular algorithms; Non-determinism; Polynomial space; State-based systems; Uncertain informations; Algorithms; Formal logic
dc.titleModular algorithms for heterogeneous modal logics via multi-sorted coalgebra
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume21
dc.date.issued2011
local.identifier.absfor080299 - Computation Theory and Mathematics not elsewhere classified
local.identifier.ariespublicationf5625xPUB7421
local.type.statusPublished Version
local.contributor.affiliationSchroder, Lutz, Universitat Bremen
local.contributor.affiliationPattinson, Dirk, College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.issue2
local.bibliographicCitation.startpage235
local.bibliographicCitation.lastpage266
local.identifier.doi10.1017/S0960129510000563
dc.date.updated2016-02-24T09:34:47Z
local.identifier.scopusID2-s2.0-80053000863
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Schroder_Modular_algorithms_for_2011.pdf1.02 MBAdobe PDF    Request a copy


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

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator