Summary: In this paper we give two equivalent characterizations of the Caucal hierarchy, a hierarchy of infinite graphs with a decidable monadic second-order (MSO) theory. It is obtained by iterating the graph transformations of unfolding and inverse rational mapping. The first characterization sticks to this hierarchical approach, replacing the language-theoretic operation of a rational mapping by an MSO-transduction and the unfolding by the treegraph operation. The second characterization is non-iterative. We show that the family of graphs of the Caucal hierarchy coincides with the family of graphs obtained as the \(\epsilon \)-closure of configuration graphs of higher-order pushdown automata.
While the different characterizations of the graph family show their robustness and thus also their importance, the characterization in terms of higher-order pushdown automata additionally yields that the graph hierarchy is indeed strict.
For the entire collection see [Zbl 1029.00064].