On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components

Giovanna D'Agostino
(University of Udine, Italy)
Giacomo Lenzi
(University of Salerno, Italy)

For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k. We show that for every k, the Modal mu-Calculus fixpoint hierarchy on SCCk collapses to the level Delta2, but not to Comp(Sigma1,Pi1) (compositions of formulas of level Sigma1 and Pi1). This contrasts with the class of all graphs, where Delta2=Comp(Sigma1,Pi1).

In Angelo Montanari, Margherita Napoli and Mimmo Parente: Proceedings First Symposium on Games, Automata, Logic, and Formal Verification (GANDALF 2010), Minori (Amalfi Coast), Italy, 17-18th June 2010, Electronic Proceedings in Theoretical Computer Science 25, pp. 55–71.
Published: 9th June 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.25.9 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org