On the structure of graphs in the Caucal hierarchy |
| |
Authors: | Achim Blumensath |
| |
Affiliation: | aTU Darmstadt, Schloßgartenstraße 7, 64289 Darmstadt, Germany |
| |
Abstract: | We investigate the structure of graphs in the Caucal hierarchy. We provide criteria concerning the degree of vertices or the length of paths which can be used to show that a given graph does not belong to a certain level of this hierarchy. Each graph in the Caucal hierarchy corresponds to the configuration graph of some higher-order pushdown automaton. The main part of the paper consists of a study of such configuration graphs. We provide tools to decompose and reassemble their runs, and we prove a pumping lemma for higher-order pushdown automata. |
| |
Keywords: | Caucal hierarchy Monadic second-order logic Higher-order pushdown automata |
本文献已被 ScienceDirect 等数据库收录! |