| Publication type: |
Article in Proceedings |
| Author: |
Lutz Schröder |
| Editor: |
Luca Aceto, Anna Ingólfsdóttir |
| Title: |
A Finite Model Construction for Coalgebraic Modal Logic |
| Book / Collection title: |
Foundations Of Software Science And Computation Structures |
| Volume: |
3921 |
| Page(s): |
157 – 171 |
| Series: |
Lecture Notes in Computer Science |
| Year published: |
2006 |
| Publisher: |
Springer, Berlin |
| Abstract: |
In recent years, a tight connection has emerged between modal logic on
the one hand and coalgebras, understood as generic transition systems,
on the other hand. Here, we prove that (finitary) coalgebraic modal
logic has the finite model property. This fact not only reproves known
completeness results for coalgebraic modal logic, which we push further
by establishing that every coalgebraic modal logic admits a complete
axiomatization of rank 1; it also enables us to establish a generic
decidability result and a first complexity bound. Examples covered by
these general results include, besides standard Hennessy-Milner logic,
graded modal logic and probabilistic modal logic.
|
| Internet: |
http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/11690634_11 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~lschrode/papers/CMLfmp.pdf |
| PostScript Version: |
http://www.informatik.uni-bremen.de/~lschrode/papers/CMLfmp.ps |
| Keywords: |
Coalgebra modal logic finite model decision procedure probabilistic modal logic |
| Note / Comment: |
EATCS Best Paper Award at ETAPS 2006 |
| Status: |
Reviewed |
| Last updated: |
02. 11. 2006 |
