Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra
Date
2011
Authors
Schroder, Lutz
Pattinson, Dirk
Journal Title
Journal ISSN
Volume Title
Publisher
Cambridge University Press
Abstract
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 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.
Description
Keywords
Keywords: Basic building block; Building blockes; Coalgebras; Decision procedure; Modal logic; Modular algorithms; Non-determinism; Polynomial space; State-based systems; Uncertain informations; Algorithms; Formal logic
Citation
Collections
Source
Mathematical Structures in Computer Science
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description