Skip to main content Skip to main navigation


A Finite Model Construction for Coalgebraic Modal Logic

Lutz Schröder
In: Luca Aceto; Anna Ingólfsdóttir (Hrsg.). Foundations Of Software Science And Computation Structures. International Conference on Foundations of Software Science and Computation Structures (FoSSaCS-2006), 9th International Conference, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2006, located at ETAPS 2006, March 25-31, Vienna, Australia, Pages 157-171, Lecture Notes in Computer Science (LNCS), Vol. 3921, ISBN 3-540-33045-3, Springer;, Berlin, 2006.


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.

Weitere Links