Universität Bremen  
  FB 3  
  Group BKB > Publications > Search > Deutsch

Publications Search - Details

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

 Back to result list
Author: Automatically generated page
  Group BKB 
Last updated: February 23, 2006   impressum