Les structures d'ordre dans la hiérarchie à pile, The structure of orders in the pushdown hierarchy

Laurent Braud

Description

Sous la direction de Didier Caucal
Thèse soutenue le 10 décembre 2010: Paris Est
Cette thèse étudie les structures dont la théorie au second ordremonadique est décidable, et en particulier la hiérarchie à pile. Onpeut définir celle-ci comme la hiérarchie pour $n$ des graphesd'automates à piles imbriquées $n$ fois ; une définition externe, partransformations de graphes, est également disponible. Nous nousintéressons à l'exemple des ordinaux. Nous montrons que les ordinauxplus petits que $epsilon_0$ sont dans la hiérarchie, ainsi que des graphesporteurs de plus d'information, que l'on appelle graphecouvrants''. Nous montrons ensuite l'inverse : tous les ordinaux de lahiérarchie sont plus petits que $epsilon_0$. Ce résultat utilise le fait queles ordres d'un niveau sont en fait isomorphes aux structures desfeuilles des arbres déterministes dans l'ordre lexicographique, aumême niveau. Plus généralement, nous obtenons une caractérisation desordres linéaires dispersés dans la hiérarchie. Dans un troisièmetemps, nous resserons l'intérêt aux ordres de type $omega$ --- les mots infinis --- pour montrer que les mots du niveau 2 sont les motsmorphiques, ce qui nous amène à une nouvelle extension au niveau 3
-Hiérarchie à pile
-Ordres linéaires
-Mots infinis
-Schémas de récursion
-Logique MSO
This thesis studies the structures with decidable monadic second-ordertheory, and in particular the pushdown hierarchy. The latter can bedefined as the family for $n$ of pushdown graphs with $n$ timesimbricated stacks ; another definition is by graph transformations. Westudy the example of ordinals. We show that ordinals smaller that $epsilon_0$are in the hierarchy, along with graphs called covering graphs'', which carry more data than ordinals. We show then the converse : allordinals of the hierarchy are smaller than $epsilon_0$. This result uses thefact that linear orders of a level are actually isomorphic to thestructure of leaves of deterministic trees by lexicographic ordering, at the same level. More generally, we obtain a characterisation ofscattered linear orders in the hierarchy. We finally focus on the caseof orders of type $omega$ --- infinite words --- and show that morphicwords are exactly words of the second level of the hierarchy. Thisleads us to a new definition of words for level 3
-Pushdown hierarchy
-Linear orders
-Infinite words
-Recursion schemes
-MSO logics
Source: http://www.theses.fr/2010PEST1009/document

Informations

• Publié par: Thesee
• Nombre de lectures: 17
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

THESE
pour obtenir le grade de
DOCTEUR DE L’UNIVERSITE PARIS-EST
The structure of orders in the pushdown hierarchy
Les structures d’ordre dans la hierarchie a pile
Specialite informatique
Ecole doctorale MSTIC
Soutenue publiquement par Laurent Braud
le 10 decembre 2010
JURY :
Zolt an Esik, rapporteur,
Wolfgang Thomas, rapporteur,
Arnaud Carayol, examinateur,
Damian Niwinski,
Dominique Perrin, examinateur,
Didier Caucal, directeur de these.
tel-00587409, version 1 - 20 Apr 20112
tel-00587409, version 1 - 20 Apr 2011Contents
1 Introduction 7
1.1 (en fran cais) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 (in English) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Preliminaries 19
2.1 Notations and rst structures . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Finite words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.4 Deterministic trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Linear orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Ordinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Scattered orderings and Hausdor rank . . . . . . . . . . . . . . . . 26
2.2.3 Orders in a deterministic tree . . . . . . . . . . . . . . . . . . . . . 29
2.3 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 First-order logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.2 Monadic second-order logic . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.3 Decidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Graph transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.1 Graph interpretations . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.2 Graph expansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5 The pushdown hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.5.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.5.2 Some properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Linear order construction 43
3.1 Ordinals in the pushdown hierarchy . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Powers of . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 n-regular presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.1 Pre x-recognizable graphs . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.2 Con guration graphs of n-hopdas . . . . . . . . . . . . . . . . . . . 49
3.3.3 Encoding ordinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3
tel-00587409, version 1 - 20 Apr 20114 CONTENTS
3.4 Covering graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.1 Fundamental sequence . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.2 Covering graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4.3 Other properties of covering graphs . . . . . . . . . . . . . . . . . . 60
3.4.4 Strictness of covering graphs in the hierarchy . . . . . . . . . . . . . 62
3.4.5 The case ofG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65"0
4 The structure of tree frontiers 67
4.1 Tree-walking automaton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 From graphs to frontiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.3 Ordinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4 Scattered linear orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.4.1 Trees with scattered frontiers . . . . . . . . . . . . . . . . . . . . . 78
4.4.2 Permutation of subtrees . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4.3 Cantor-Bendixson rank of deterministic trees . . . . . . . . . . . . . 81
4.4.4 Hausdor rank of scattered orders in Graph . . . . . . . . . . . . . 86n
4.5 Finite combs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5 Schemes and morphic words 91
5.1 Recursion schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.1.1 De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.1.2 Schemes in the pushdown hierarchy . . . . . . . . . . . . . . . . . . 94
5.2 Morphic words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.1 De nition and properties . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.2 Construction in the pushdown hierarchy . . . . . . . . . . . . . . . 99
5.2.3 Words in Graph are morphic, direct proof . . . . . . . . . . . . . . 992
5.2.4 Words in Graph are by recursion schemes . . . . . . . . . 1022
5.3 Second order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.3.1 Second-order morphic words . . . . . . . . . . . . . . . . . . . . . . 106
5.3.2 scheme !-frontiers . . . . . . . . . . . . . . . . . . . . 109
5.3.3 Liouville word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
List of notations 119
Index 121
Bibliography 123
tel-00587409, version 1 - 20 Apr 2011List of Figures
1.1 Un graphe ni et une propriete de ce graphe. . . . . . . . . . . . . . . . . . 7
1.2 L’arbre binaire complet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 A nite graph and one of its properties. . . . . . . . . . . . . . . . . . . . . 13
1.4 The complete binary tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1 Example of a graph : the ladder . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 The graph representation of the ordinal ! + 2. . . . . . . . . . . . . . . . . 24
2.3 The ladder and its unfolding. . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Treegraph of the complete binary tree. . . . . . . . . . . . . . . . . . . . . 36
2.5 The pushdown hierarchy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.6 Exemple of graph constructions in the hierarchy. . . . . . . . . . . . . . . . 39
33.1 Finite graph G which unfolding has frontier ! . . . . . . . . . . . . . . . . 443
3.2 Folded graphs of trees of frontier , and !(1 +). . . . . . . . . . . . . . 45
!3.3 Folded regular graph of a tree of frontier . . . . . . . . . . . . . . . . . . 46
3.4 f0; 1g-treegraph of !. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
!3.5 The operation inc(! ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
!3.6 Covering graph of ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.7 Exponentiation of the covering graph of !. . . . . . . . . . . . . . . . . . . 62
4.1 Order in a nite tree t and \arranged" tree s(t). . . . . . . . . . . . . . . . 72
4.2 Non-full tree of frontier ! having a branch with in nitely many 0’s. . . . . 74
4.3 A nite graph G, \spanning tree" T , completed tree T , and unfolding. . . . 76
4.4 Orders in a tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
!5.1 Rules for S , of frontier ! . . . . . . . . . . . . . . . . . . . . . . . . . . . 951
5.2 General rules for S , of frontier !"" (n + 1). . . . . . . . . . . . . . . . . 95n
5.3 Paperfolding sequence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
i25.4 A graph which unfolding yields the morphic word abaab:::a b::: . . . . . 100
5.5 General shape of the folded graph. . . . . . . . . . . . . . . . . . . . . . . 101
5.6 Rules of a scheme which frontier is a morphic word. . . . . . . . . . . . . . 105
5.7 Order-2 safe scheme which frontier is the Champernowne word. . . . . . . 107
5.8 safe scheme which frontier is the Liouville word. . . . . . . . . . . 118
5
tel-00587409, version 1 - 20 Apr 20116 LIST OF FIGURES
tel-00587409, version 1 - 20 Apr 2011Chapter 1
Introduction
1.1 (en fran cais)
En logique mathematique, on distingue les objets mathematiques, ou structures, et leurs
proprietes, ou logique. Les structures a leur tour sont constituees d’elements et de relations
entre ces elements. Dans cette these, nous travaillerons uniquement sur ce que l’on appelle
des \graphes colores dont les arcs sont etiquetes", c’est- a-dire des structures dont les
relations sont d’arite au plus 2. De plus, ces structures seront denombrables | on peut
numeroter chaque objet avec un entier | et de presentation nie | il existe une quantite
nie d’information permettant de representer la structure de fa con non ambigue.
\Un chemin entre deux sommets blancs est en
pointilles ou passe par un sommet noir."
Figure 1.1: Un graphe ni et une propriete de ce graphe.
La logique la plus simple est celle dite du premier ordre, car elle manipule simplement
les elements proprement dits de la structure consideree. Elle permet d’exprimer des
proprietes du type \tout sommet colorie en noir a un voisin blanc" ou \s’il existe un
sommet blanc, alors il existe 3 arcs distincts en pointilles". Elle est cependant restreinte
a des proprietes ponctuelles et ne dit rien sur la structure dans sa globalite. Une solution
est alors de considerer une logique plus forte, qui permet de manipuler directement des
ensembles d’elements. C’