**The Mu-Calculus Alternation Hierarchy Collapses over Structures with Restricted Connectivity**

**Abstract**
The alternation hierarchy of least and greatest fixpoint operators in the mu-calculus is strict. However, the
strictness of the hierarchy does not necessarily carry over when considering restricted classes of structures.
For instance, over the class of infinite words the alternation-free fragment of the mu-calculus is already as
expressive as the full logic. Our current understanding of when and why the mu-calculus alternation hierarchy
is (and is not) strict is limited. This article makes progress in answering these questions by showing that
the alternation hierarchy of the mu-calculus collapses to the alternation-free fragment over some classes of
structures, including infinite nested words and finite graphs with feedback vertex sets of a bounded size.
Common to these classes is that the connectivity between the components in a structure from such a class
is restricted in the sense that the removal of certain vertices from the graph of the structure decomposes it into
graphs in which all paths are of finite length. The collapse results herein are obtained in an automatatheoretic
setting. They subsume, generalize, and strengthen several prior results on the expressivity of the
mu-calculus over restricted classes of structures.

This article appears in the special issue of the Theoretical Computer Science journal dedicated to selected papers presented at GANDALF 2012. (PDF , Elsevier)