| Publication type: |
Article in Proceedings |
| Author: |
Lutz Schröder, Dirk Pattinson |
| Editor: |
Lars Arge, Andrzej Tarlecki, Christian Cachin |
| Title: |
Modular Algorithms for Heterogeneous Modal Logics |
| Book / Collection title: |
Automata, Languages and Programming (ICALP 07) |
| Volume: |
4596 |
| Page(s): |
459 – 471 |
| Series: |
Lecture Notes in Computer Science |
| Year published: |
2007 |
| Publisher: |
Springer |
| Abstract: |
State-based systems and modal logics for reasoning about them often
heterogeneously combine a number of features such as non-determinism and
probabilities. Here, we show that the combination of features can
be reflected algorithmically and 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 an algorithmic description to 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 that this is 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 e.g. Segala systems and games with uncertain information.
|
| Internet: |
http://dx.doi.org/10.1007/978-3-540-73420-8_41 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~lschrode/papers/ModularAlgs.pdf |
| Keywords: |
modal logic multisorted coalgebra complexity modularity Segala systems fusion |
| Status: |
Reviewed |
| Last updated: |
18. 06. 2008 |
