The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. (English) Zbl 1205.03022
Pandya, Paritosh K. (ed.) et al., FST TCS 2003: Foundations of software technology and theoretical computer science. 23rd conference, Mumbai, India, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20680-9/pbk). Lect. Notes Comput. Sci. 2914, 112-123 (2003).
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].
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].
MSC:
03B25 | Decidability of theories and sets of sentences |
03D05 | Automata and formal grammars in connection with logical questions |
68Q45 | Formal languages and automata |
68R10 | Graph theory (including graph drawing) in computer science |