On Modal mu-Calculus over finite graphs with small components or small tree width

This paper is a continuation and correction of a paper presented by the same authors at the conference GANDALF 2010. We consider the Modal mu-calculus and some fragments of it. For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k, and the class TWk of all finite graphs of tree width at most k. As upper bounds, we show that for every k, the temporal logic CTL* collapses to alternation free mu-calculus in SCCk; and in TW1, the winning condition for parity games of any index n belongs to the level Delta(2) of Modal mu-calculus. As lower bounds, we show that Buchi automata are not closed under complement in TW2 and coBuchi nondeterministic and alternating automata differ in TW1.