The modal μ-calculus hierarchy over restricted classes of transition systems

Alberucci, Luca and Facchini, Alessandro (2009) The modal μ-calculus hierarchy over restricted classes of transition systems. Journal of Symbolic Logic, 74 (4). pp. 1367-1400. ISSN 0022-4812

[img] Text
af09b.pdf - Draft Version

Download (371kB)

Abstract

We study 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 nite model theorem for reflexive systems the same results holds for nite models. Second, we prove that over transitive systems the hierarchy collapses to the alternation-free fragment. In order to do this the nite 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.

Actions (login required)

View Item View Item