@InProceedings{   CarayolWohrle:FSTTCS:2003,
  Author        = {Carayol, Arnaud and W{\"o}hrle, Stefan},
  Editor        = "Pandya, Paritosh K. and Radhakrishnan, Jaikumar",
  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 $\epsilon$-closure of configuration graphs of higher-order pushdown automata.",
  Address       = "Berlin, Heidelberg",
  BookTitle     = "Proc. of FSTTCS'03",
  date-added    = "2020-01-27 17:14:42 +0100",
  date-modified = "2020-02-05 17:46:36 +0100",
  ISBN          = "978-3-540-24597-1",
  Pages         = "112--123",
  Publisher     = "Springer Berlin Heidelberg",
  Title         = "The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata",
  Year          = "2003",
  File          = "The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-order Pushdown Automata - cawo03 - a - a - a - o.pdf"
}

@InProceedings{ CarayolWohrle:FSTTCS:2003, Author = {Carayol, Arnaud and W{\"o}hrle, Stefan}, Editor = "Pandya, Paritosh K. and Radhakrishnan, Jaikumar", 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 $\epsilon$-closure of configuration graphs of higher-order pushdown automata.", Address = "Berlin, Heidelberg", BookTitle = "Proc. of FSTTCS'03", date-added = "2020-01-27 17:14:42 +0100", date-modified = "2020-02-05 17:46:36 +0100", ISBN = "978-3-540-24597-1", Pages = "112--123", Publisher = "Springer Berlin Heidelberg", Title = "The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata", Year = "2003", File = "The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-order Pushdown Automata - cawo03 - a - a - a - o.pdf" }