?. , ?. Prefix-relation, and .. , 19 ? " not prefix " symmetric relation 19 ¯ a reverse arc label, p.34

G. Finite-order-types, .. , Z. , and Q. , 23 ?, ?, ? order types of, MTh(G) monadic theory of the structure, p.23

K. Kleene-brouwer-ordering and .. , 29 ? isomorphism up to subtree permutation, p.79

?. Cantor-bendixson-derivative and .. , 81?r 81? 81?r CB alternative version of the Cantor-Bendixson rank 82 K f tree of the function f 62 Covering graphs ?[n] element of the fundamental sequence of ? 55 ? covering graph relation, 55 G ? covering graph of ?, p.56

A. Aho and J. Ullman, Translations on a context free grammar, Information and Control, vol.19, issue.5, pp.439-475, 1971.
DOI : 10.1016/S0019-9958(71)90706-6

V. Bárány, -Words having a Decidable MSO Theory, RAIRO - Theoretical Informatics and Applications, vol.42, issue.3, pp.417-450, 2008.
DOI : 10.1051/ita:2008008

S. Bloom and C. Choffrut, Long words: the theory of concatenation and ??-power, Theoretical Computer Science, vol.259, issue.1-2, pp.533-548, 2001.
DOI : 10.1016/S0304-3975(00)00040-2

[. Bruyère and O. Carton, Hierarchy among automata on linear orderings, Proc. of IFIP, pp.107-118, 2002.

B. Alexis, O. Es, and . Carton, A Kleene theorem for languages of words indexed by linear orderings, International Journal of Foundations of Computer Science, vol.17, issue.3, pp.519-542, 2006.

[. Bojanczyk and T. Colcombet, Tree-walking automata cannot be determinized, Theoretical Computer Science, vol.350, issue.2-3, pp.164-173, 2006.
DOI : 10.1016/j.tcs.2005.10.031

[. Bruyère and O. Carton, Automata on linear orderings, Journal of Computer and System Sciences, vol.73, issue.1, pp.1-24, 2007.
DOI : 10.1016/j.jcss.2006.10.009

[. Bojanczyk and T. Colcombet, Tree-walking automata do not recognize all regular languages, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing , STOC '05, pp.658-701, 2008.
DOI : 10.1145/1060590.1060626
URL : https://hal.archives-ouvertes.fr/hal-00347182

L. Braud and A. Carayol, Linear Orders in the Pushdown Hierarchy
DOI : 10.1007/978-3-642-14162-1_8
URL : https://hal.archives-ouvertes.fr/hal-00733438

S. Bloom and Z. , Scattered algebraic linear orderings, Proc. of FICS, pp.25-30, 2009.

S. Bloom and Z. , Algebraic ordinals, Fundamenta Informaticae, vol.99, issue.4, pp.383-407, 2010.
DOI : 10.1007/978-3-540-73859-6_1

A. Blumensath, On the structure of graphs in the Caucal hierarchy, Theoretical Computer Science, vol.400, issue.1-3, pp.19-45, 2008.
DOI : 10.1016/j.tcs.2008.01.053

D. Bojanczyk, A. Niwi´nskiniwi´nski, and . Rabinovich, Adam Radziwonczyk-Syta, and Michal Skrzypczak. On the Borel complexity of MSO definable sets of branches, Fundamenta Informaticae, vol.98, issue.4, pp.337-349, 2010.

[. Bojanczyk, Tree-Walking Automata, Proc. of LATA, pp.1-2, 2008.
DOI : 10.1007/978-3-540-88282-4_1
URL : https://hal.archives-ouvertes.fr/hal-00347182

L. Braud, Order-2 morphic words and recursion schemes

L. Braud, Covering of ordinals, Proc. of FSTTCS, pp.97-108, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00620312

R. Büchi, On a decision method in the restricted second-order arithmetic . Logic, Methodology and Philosophy of science, Proc. Intern. Congr, pp.1-11, 1962.

R. Büchi, The monadic second order theory of ??1, Lecture Notes in Mathematics, vol.76, pp.1-217, 1973.
DOI : 10.1007/978-3-662-36678-3

R. Büchi, Decision methods in the theory of ordinals, Bulletin of the American Mathematical Society, vol.71, issue.5, pp.767-770, 1965.
DOI : 10.1090/S0002-9904-1965-11384-2

[. Cachat, Tree Automata Make Ordinal Theory Easy, Proc. of FSTTCS, pp.285-296, 2006.
DOI : 10.1007/11944836_27
URL : https://hal.archives-ouvertes.fr/hal-00110485

G. Cantor, Beiträge zur begründung der transfiniten mengenlehre Two-parts article. Translated in french by F. Marotte, Mathematische Annalen, vol.4649, pp.481-512, 1895.
DOI : 10.1007/bf02124929

A. Carayol, Regular Sets of Higher-Order Pushdown Stacks, Proc. of MFCS, pp.168-179, 2005.
DOI : 10.1007/11549345_16
URL : https://hal.archives-ouvertes.fr/hal-00620141

A. Carayol, Automates infinis, logiques et langages, 2006.
URL : https://hal.archives-ouvertes.fr/tel-00628513

[. Caucal, On the regular structure of prefix rewriting, Theoretical Computer Science, vol.106, issue.1, pp.61-86, 1992.
DOI : 10.1016/0304-3975(92)90278-N

[. Caucal, On infinite transition graphs having a decidable monadic theory, Proc. of ICALP, pp.194-205, 1996.
DOI : 10.1007/3-540-61440-0_128

D. Caucal, On Infinite Terms Having a Decidable Monadic Theory, Proc. of MFCS, pp.165-176
DOI : 10.1007/3-540-45687-2_13

[. Caucal, On infinite transition graphs having a decidable monadic theory, Theoretical Computer Science, vol.290, issue.1, pp.79-115, 2003.
DOI : 10.1016/S0304-3975(01)00089-5

[. Champernowne, The Construction of Decimals Normal in the Scale of Ten, Journal of the London Mathematical Society, vol.1, issue.4, pp.254-260, 1933.
DOI : 10.1112/jlms/s1-8.4.254

A. Church, The constructive second number class, Bulletin of the American Mathematical Society, vol.44, issue.4, pp.224-232, 1938.
DOI : 10.1090/S0002-9904-1938-06720-1
URL : http://projecteuclid.org/download/pdf_1/euclid.bams/1183500400

[. Caucal and T. Knapik, An Internal Presentation of Regular Graphs by Prefix-Recognizable Graphs, Theory of Computing Systems, vol.34, issue.4, pp.299-336, 2001.
DOI : 10.1007/s00224-001-1015-5

[. Courcelle and T. Knapik, The evaluation of first-order substitution is monadic second-order compatible, Theoretical Computer Science, vol.281, issue.1-2, pp.177-206, 2002.
DOI : 10.1016/S0304-3975(02)00012-9

T. Colcombet and C. Löding, Transforming structures by set interpretations, Logical Methods in Computer Science, vol.3, issue.2, pp.3-5, 2007.
DOI : 10.2168/LMCS-3(2:4)2007
URL : https://hal.archives-ouvertes.fr/hal-00192051

[. Courcelle, Frontiers of infinite trees, RAIRO. Informatique th??orique, vol.12, issue.4, 1978.
DOI : 10.1051/ita/1978120403191

[. Courcelle, Graph Rewriting: An Algebraic and Logic Approach, Handbook of TCS, Volume B: Formal Models and Semantics, pp.193-242, 1990.
DOI : 10.1016/B978-0-444-88074-1.50010-X

[. Courcelle, Monadic second-order definable graph transductions: a survey, Theoretical Computer Science, vol.126, issue.1, pp.53-75, 1994.
DOI : 10.1016/0304-3975(94)90268-2

[. Courcelle, Graph structure and monadic second-order logic, 2011.
DOI : 10.1017/CBO9780511977619
URL : https://hal.archives-ouvertes.fr/hal-00646514

W. Olivier-carton and . Thomas, The Monadic Theory of Morphic Infinite Words and Generalizations, Information and Computation, vol.176, issue.1, pp.51-65, 2002.
DOI : 10.1006/inco.2001.3139

[. Courcelle and I. Walukiewicz, Monadic second-order logic, graph coverings and unfoldings of transition systems, Annals of Pure and Applied Logic, vol.92, issue.1, pp.35-62, 1998.
DOI : 10.1016/S0168-0072(97)00048-1

A. Carayol and S. Wöhrle, The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata, Proc. of FSTTCS, pp.112-123, 2003.
DOI : 10.1007/978-3-540-24597-1_10

W. Damm, Languages defined by higher type program schemes, Proc. of ICALP, pp.164-179, 1977.
DOI : 10.1007/3-540-08342-1_13

W. Damm, The IO- and OI-hierarchies, Theoretical Computer Science, vol.20, issue.2, pp.95-207, 1982.
DOI : 10.1016/0304-3975(82)90009-3

S. Fratani, AutomatesàAutomatesà piles de piles... de piles, 2005.

[. Fratani and G. Sénizergues, Iterated pushdown automata and sequences of rational numbers, Annals of Pure and Applied Logic, vol.141, issue.3, pp.363-411, 2006.
DOI : 10.1016/j.apal.2005.12.004
URL : https://hal.archives-ouvertes.fr/hal-00368254

H. Gaifman, On Local and Non-Local Properties, Proceedings of the Herbrand Symposium, volume 107 of Studies in Logic and the Foundations of Mathematics, pp.105-135, 1982.
DOI : 10.1016/S0049-237X(08)71879-2

Y. Gurevich, Monadic second-order theories. Model-Theoretic Logic, pp.479-506, 1985.
DOI : 10.1017/9781316717158.019

[. Hausdorff, Grundz???ge einer Theorie der geordneten Mengen, Mathematische Annalen, vol.65, issue.4, pp.435-505, 1908.
DOI : 10.1007/BF01451165

[. Heilbrunner, An algorithm for the solution of fixed-point equations for infinite words, RAIRO. Informatique th??orique, vol.14, issue.2, pp.131-141, 1980.
DOI : 10.1051/ita/1980140201311

I. Ianov, The logical schemes of algorithms. English translation in Problems of Cybernetics, pp.82-140, 1960.

A. S. Kechris, Classical Descriptive Set Theory, 1994.
DOI : 10.1007/978-1-4612-4190-4

S. Kleene, On notation for ordinal numbers, The Journal of Symbolic Logic, vol.28, issue.04, pp.150-155, 1938.
DOI : 10.1215/S0012-7094-36-00227-2

D. Knuth, Mathematics and Computer Science: Coping with Finiteness, Science, vol.194, issue.4271, pp.1235-1242, 1976.
DOI : 10.1126/science.194.4271.1235

T. Knapik, D. Niwi´nskiniwi´nski, and . Urzyczyn, Deciding Monadic Theories of Hyperalgebraic Trees, Proc. of TLCA, pp.253-267, 2001.
DOI : 10.1007/3-540-45413-6_21

T. Knapik, D. Niwi´nskiniwi´nski, and . Urzyczyn, Higher-Order Pushdown Trees Are Easy, Proc. of FoSSaCS, pp.205-222, 2002.
DOI : 10.1007/3-540-45931-6_15
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.5773

[. Knapik, D. Niwinski, P. Urzyczyn, and I. Walukiewicz, Unsafe Grammars and Panic Automata, Proc. of ICALP, pp.1450-1461, 2005.
DOI : 10.1007/11523468_117
URL : https://hal.archives-ouvertes.fr/hal-00335729

[. Khoussainov, S. Rubin, and F. Stephan, Automatic linear orders and trees, ACM Transactions on Computational Logic, vol.6, issue.4, pp.675-700, 2005.
DOI : 10.1145/1094622.1094625

[. Lavergne, Prédicats algébriques d'entiers, 2005.

N. Marin, Suites de mots et automates, 2007.

]. A. Mas74 and . Maslov, The hierarchy of indexed languages of an arbitrary level, Soviet Math. Dokl, vol.15, pp.1170-1174, 1974.

D. Muller and P. Schupp, The theory of ends, pushdown automata, and second-order logic, Theoretical Computer Science, vol.37, issue.1, pp.51-75, 1985.
DOI : 10.1016/0304-3975(85)90087-8

M. Nivat, Langages algébriques sur le magma libre et sémantique des schémas de programme, Proc. of ICALP, pp.293-308, 1972.

M. Nivat and D. Perrin, Ensembles reconnaissables de mots biinfinis, Proc. of STOC, pp.47-59, 1982.
DOI : 10.1145/800070.802176

L. Ong, On Model-Checking Trees Generated by Higher-Order Recursion Schemes, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), pp.81-90, 2006.
DOI : 10.1109/LICS.2006.38
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.7084

P. Pawe, Collapse operation increases expressive power of deterministic higher order pushdown automata, 2010.

J. Pillot, Produits de graphes infinis et logique monadique, 2004.

M. Rabin, Decidability of second-order theories and automata on infinite trees. Transaction of the AMS, pp.1-35, 1969.

H. Rogers, Theory of recursive functions and effective computability, 1987.

[. Roitman, Introduction to Modern Set Theory, 1990.

G. Joseph and . Rosenstein, Linear orderings, 1982.

A. Rabinovich and A. Shomrat, Abstract, The Journal of Symbolic Logic, vol.6, issue.03, pp.783-816, 2008.
DOI : 10.1007/BFb0082721

[. Seese, The structure of the models of decidable monadic theories of graphs. Annals of pure and applied logic, pp.169-195, 1991.

A. Semenov, Decidability of monadic theories, Proc. of MFCS, pp.162-175, 1984.
DOI : 10.1007/BFb0030296

[. Shelah, The Monadic Theory of Order, The Annals of Mathematics, vol.102, issue.3, pp.379-419, 1975.
DOI : 10.2307/1971037

[. Thomas, On frontiers of regular trees, RAIRO - Theoretical Informatics and Applications, vol.20, issue.4, pp.371-381, 1986.
DOI : 10.1051/ita/1986200403711

[. Thomas, Ehrenfeucht games, the composition method, and the monadic theory of ordinal words, Structures in Logic and Computer Science, pp.118-143, 1997.
DOI : 10.1007/3-540-63246-8_8

W. Thomas and . Languages, In Handbook of Formal Language Theory, volume III, pp.389-455, 1997.

[. Thomas, Model Transformations in Decidability Proofs for Monadic Theories, Proc. of CSL, pp.23-31, 2008.
DOI : 10.1007/978-3-540-87531-4_3

O. Veblen, Continuous increasing functions of finite and transfinite ordinals, Transactions of the American Mathematical Society, vol.9, issue.3, pp.280-292, 1908.
DOI : 10.1090/S0002-9947-1908-1500814-9

[. Walukiewicz, Monadic second-order logic on tree-like structures, Theoretical Computer Science, vol.275, issue.1-2, pp.311-346, 2002.
DOI : 10.1016/S0304-3975(01)00185-2
URL : http://doi.org/10.1016/s0304-3975(01)00185-2

. Wies and . Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinite trees, Theoretical Computer Science, vol.200, pp.135-183, 1998.