Abstract
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 ε-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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blumensath, A.: Prefix-recognisable graphs and monadic second-order logic. Technical Report AIB-2001-06, RWTH Aachen (2001)
Cachat, T.: Higher order pushdown automata, the Caucal hierarchy of graphs and parity games. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 556–569. Springer, Heidelberg (2003)
Carayol, A., Colcombet, T.: On equivalent representations of infinite structures. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 599–610. Springer, Heidelberg (2003)
Carayol, A., Wöhrle, S.: The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. Technical report, RWTH Aachen (2003)
Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 275–284. Springer, Heidelberg (2000)
Caucal, D.: On infinite transition graphs having a decidable monadic theory. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 194–205. Springer, Heidelberg (1996)
Caucal, D.: On infinite terms having a decidable monadic theory. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 165–176. Springer, Heidelberg (2002)
Courcelle, B.: Monadic second-order definable graph transductions: A survey. Theoretical Computer Science 126, 53–75 (1994)
Courcelle, B., Walukiewicz, I.: Monadic second-order logic, graph coverings and unfoldings of transition systems. Annals of Pure and Applied Logic 92, 35–62 (1998)
Damm, W.: An algebraic extension of the Chomsky-hierarchy. In: Proceedings of the 8th International Symposium on Mathematical Foundations of Computer Science. LNCS, vol. 74, pp. 266–276. Springer, Heidelberg (1979)
Damm, W.: The IO and OI hierarchies. Theoretical Computer Science 20, 95–208 (1982)
Damm, W., Goerdt, A.: An automata-theoretical characterization of the OI hierarchy. Information and Control 71, 1–32 (1986)
Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)
Engelfriet, J.: Iterated stack automata and complexity classes. Information and Computation 95, 21–75 (1991)
Knapik, T., Niwiński, D., Urzyczyn, P.: Higher-order pusdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. T. Knapik, D. Niwiński, and P. Urzyczyn, vol. 2303, pp. 205–222. Springer, Heidelberg (2002)
Stirling, C.: Decidability of bisimulation equivalence for pushdown processes (submitted)
Thomas, W.: Constructing infinite graphs with a decidable MSO-theory. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 113–124. Springer, Heidelberg (2003)
Walukiewicz, I.: Monadic second-order logic on tree-like structures. Theoretical Computer Science 275, 311–346 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carayol, A., Wöhrle, S. (2003). The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata. In: Pandya, P.K., Radhakrishnan, J. (eds) FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2003. Lecture Notes in Computer Science, vol 2914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24597-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-24597-1_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20680-4
Online ISBN: 978-3-540-24597-1
eBook Packages: Springer Book Archive