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

**Abstract**
It is known that the alternation hierarchy of least and greatest fixpoint operators in the mu-calculus is
strict. However, the strictness of the alternation hierarchy does not necessarily carry over when considering
restricted classes of structures. A prominent instance is the class of infinite words over which
the alternation-free fragment is already as expressive as the full mu-calculus. Our current understanding of
when and why the mu-calculus alternation hierarchy is not strict is limited. This paper 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 structure of the graph decomposes it into graphs in which all
paths are of finite length. Our collapse results are obtained in an automata-theoretic setting. They
subsume, generalize, and strengthen several prior results on the expressivity of the mu-calculus over
restricted classes of structures.

Full Article (PDF , EPTCS)