The Modal μ-Calculus Hierarchy on Restricted Classes of Transition Systems

Details

Ressource 1Download: BIB_9EAD16376E0A.P001.pdf (347.44 [Ko])
State: Public
Version: author
Serval ID
serval:BIB_9EAD16376E0A
Type
Article: article from journal or magazin.
Collection
Publications
Institution
Title
The Modal μ-Calculus Hierarchy on Restricted Classes of Transition Systems
Journal
The Journal of Symbolic Logic
Author(s)
Facchini A., Alberucci L.
Publication state
Published
Issued date
2009
Peer-reviewed
Oui
Volume
74
Number
4
Pages
1367-1400
Language
english
Abstract
We discuss the strictness of the modal µ-calculus hierarchy over some restricted classes of transition systems. First, we show that the hierarchy is strict over reflexive frames. By proving the finite model theorem for reflexive systems the same results holds for finite models. Second, we prove that over transitive systems the hierarchy collapses to the alternation-free fragment. In order to do this the finite model theorem for transitive transition systems is also proved. Further, we verify that if symmetry is added to transitivity the hierarchy collapses to the purely modal fragment.
Create date
17/12/2008 9:22
Last modification date
20/08/2019 15:04
Usage data