Room 327

Order 2 tree-automatic graphs

Antoine Meyer

University Paris Est-Marne la Vallee

In 2007, Colcombet and Löding proposed a higher-order generalization of tree-automatic graphs, obtained by applying a certain class of logical interpretations to the graphs generated by higher-order pushdown automata. In this ongoing work with Arnaud Carayol, we propose a direct automata-theoretic definition of these graphs, which coincides at order 1 with the usual definition based on synchronized tree transducers. As an application, we aim to characterize the languages of order n tree-automatic graphs seen as infinite automata. This talk will focus mostly on the second level of the hierarchy.