The modal \(\mu \)-calculus hierarchy over restricted classes of transition systems. (English) Zbl 1191.03012

It is well known that the alternation hierarchy of the modal \(\mu\)-calculus is strict, cf. [J. C. Bradfield, Theor. Comput. Sci. 195, No. 2, 133–153 (1998; Zbl 0915.03017)]. In this paper, the authors study the alternation hierarchy of the modal \(\mu\)-calculus over restricted classes of transition systems.
The main result of the paper is that the modal \(\mu\)-calculus hierarchy over transitive transition systems is strict. In order to obtain this result, the authors provide an explicit syntactical translation of the full modal \(\mu\)-calculus into the alternation-free fragment. Furthermore, the authors show that the modal \(\mu\)-calculus hierarchy over reflexive transition systems is strict as well. The proof is a modification of a proof of the strictness of the \(\mu\)-calculus hierarchy over the class of binary transition systems by A. Arnold [Theor. Inform. Appl. 33, No. 4–5, 329–339 (1999; Zbl 0945.68118)] and L. Alberucci [Lect. Notes Comput. Sci. 2500, 185–201, 365–376 (2002; Zbl 1021.03012)].
Other results in this article are finite model theorems for reflexive and for transitive transition systems and a proof of the fact that the modal \(\mu\)-calculus over the class of transitive and symmetric transition systems collapses to its purely modal fragment.


03B45 Modal logic (including the logic of norms)
03B70 Logic in computer science
05C57 Games on graphs (graph-theoretic aspects)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI


[1] Gödel ’96 (Brno, 1996) 6 pp 139– (1996)
[2] Annals of Pure and Applied Logic
[3] Methods for modalities (2007)
[4] DOI: 10.2140/pjm.1955.5.285 · Zbl 0064.26004
[5] DOI: 10.1016/0890-5401(89)90031-X · Zbl 0671.03023
[6] Modal and temporal properties of processes (2001)
[7] A theory of programs (1969)
[8] DOI: 10.1016/B978-044482830-9/50022-9
[9] STACS, 1998 pp 39– (1998)
[10] DOI: 10.1016/S0304-3975(97)00217-X · Zbl 0915.03017
[11] Modal logic (2001) · Zbl 0998.03015
[12] ITA 33 pp 329– (1999)
[13] DOI: 10.1007/s11225-009-9170-9 · Zbl 1201.03008
[14] Bulletin of the Belgian Mathematical Society 8 pp 359– (2001)
[15] DOI: 10.1016/S0304-3975(01)00185-2 · Zbl 1026.68087
[16] Processes, terms and cycles, steps on the road to infinity, essays dedicated to Jan Willem Klop on the occasion of his 60th birthday pp 14– (2005) · Zbl 1097.68007
[17] WSEAS Transactions on Mathematics 5 pp 1021– (2006)
[18] Games with forbidden position (1991)
[19] ICALP, 1996 pp 87– (1996)
[20] DOI: 10.1007/BF00370554 · Zbl 0667.03019
[21] DOI: 10.1016/0304-3975(82)90125-6 · Zbl 0553.03007
[22] A new introduction to modal logic (1996) · Zbl 0855.03002
[23] Automata, logics, and infinite games (2002)
[24] FOCS, 1991 pp 368– (1991)
[25] DOI: 10.1007/s11225-006-8301-9 · Zbl 1106.03017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.