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

Alberucci, Luca; Facchini, Alessandro

J. Symb. Log. 74, No. 4, 1367-1400 (2009).

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.

Reviewer: Clemens Kupke (London)

MSC:

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.)

Keywords:

modal logic; modal \(\mu\)-calculus; parity games; alternation hierarchy; transition systems

Citations:

Zbl 0915.03017; Zbl 0945.68118; Zbl 1021.03012

References:

[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