Project topics and materials
Get Complete Project Material File(s) Now! »
The pushdown hierarchy
The pushdown hierarchy — sometimes called the Caucal hierarchy — is a family of sets of graphs having a decidable monadic theory. It covers actually two families : one noted (Graphn)n≥0, and one only composed of trees, noted (Treen)n≥0. For all n ≥ 0, we have Treen ⊆ Graphn, Treen ⊆ Treen+1, and Graphn ⊆ Graphn+1. As stated in the introduction, the history of the pushdown hierarchy starts with the result of Muller and Schupp [MS85] about a geometrical property on configuration graphs of pushdown automata from a given configuration. The graph decomposition of a graph G from a vertex r ∈ VG is the family of the connected components of the subgraphs (Gr,n)n≥0. The nth decomposition Gr,n is the subgraph which support is the set of vertices at distance at least n of r. The graph is said finitely decomposable if, for any vertex r, the graph decomposition is finite up to isomorphism. Example 2.5.1. If we decompose the complete binary tree from its root, the graph decomposition is reduced to the singleton of the binary tree itself. More generally, if we decompose this tree from a vertex of depth k, the cardinal of the graph decomposition is k + 1. N
Tree-walking automaton
It is well-known that on deterministic trees MSO logic is captured by parity tree automata [Rab69]. This equivalence can be used to characterize the binary relations defined by MSO formulæ on such trees using a finite state automaton running on the tree. The tree-walking automata is not new [AU71], but they have mostly been used on finite trees [BC08, BC06b]; see [Boj08] for a survey. Here, we use these automata on infinite trees as a “weak form” of monadic interpretations.
Definition. A non-deterministic tree-walking automaton or simply TWA working on deterministic trees over Σ colored by Γ is a tuple A = (Q, q0, F,Δ) where Q is the finite set of states, q0 ∈ Q is the initial state, F is the set of final states and Δ is the set of transitions. A transition is a tuple (p, c, q, a) with.
• p ∈ Q is the current state,
• c ∈ Γ is the color of the current node,
• q ∈ Q is the next state,
• a ∈ Σ ∪ {ε, ↑} is the action to perform. Intuitively ε corresponds to “staying in the current node”, ↑ to “going to the parent node” and d ∈ Σ corresponds to “going to the d-son”.
Scattered linear orders
In Section 3.2, we have proved that any power by α < ω ↑↑ n of ζ is actually in Graphn. In the other way around, we consider the scattered linear orders in the pushdown hierarchy. Using the result of the previous section, we characterize the Hausdorff rank of scattered orderings of the hierarchy : this is Theorem 4.4.12.To reach this result, we begin with a general proposition on trees have a scattered frontier. Then we notice that we may recursively switch subtrees of such a tree to obtain an ordinal frontier. This does not change the mesure based on the number of infinite branches in the tree, called Cantor-Bendixson rank of the tree. It is then sufficient to prove that this CB-rank is tightly related to the Hausdorff rank, which allows us to conclude.
Table of contents :
1 Introduction
1.1 (en fran¸cais)
1.2 (in English)
2 Preliminaries
2.1 Notations and first structures
2.1.1 Finite words
2.1.2 Structures
2.1.3 Graphs
2.1.4 Deterministic trees
2.2 Linear orderings
2.2.1 Ordinals
2.2.2 Scattered orderings and Hausdorff rank
2.2.3 Orders in a deterministic tree
2.3 Logic
2.3.1 First-order logic
2.3.2 Monadic second-order logic
2.3.3 Decidability
2.4 Graph transformations
2.4.1 Graph interpretations
2.4.2 Graph expansions
2.5 The pushdown hierarchy
2.5.1 Definition
2.5.2 Some properties
3 Linear order construction
3.1 Ordinals in the pushdown hierarchy
3.2 Powers of ζ
3.3 n-regular presentation
3.3.1 Prefix-recognizable graphs
3.3.2 Configuration graphs of n-hopdas
3.3.3 Encoding ordinals
3.4 Covering graphs
3.4.1 Fundamental sequence
3.4.2 Covering graphs
3.4.3 Other properties of covering graphs
3.4.4 Strictness of covering graphs in the hierarchy
3.4.5 The case of Gε0
4 The structure of tree frontiers
4.1 Tree-walking automaton
4.2 From graphs to frontiers
4.3 Ordinals
4.4 Scattered linear orders
4.4.1 Trees with scattered frontiers
4.4.2 Permutation of subtrees
4.4.3 Cantor-Bendixson rank of deterministic trees
4.4.4 Hausdorff rank of scattered orders in Graphn
4.5 Finite combs
5 Schemes and morphic words
5.1 Recursion schemes
5.1.1 Definition
5.1.2 Schemes in the pushdown hierarchy
5.2 Morphic words
5.2.1 Definition and properties
5.2.2 Construction in the pushdown hierarchy
5.2.3 Words in Graph2 are morphic, direct proof
5.2.4 Words in Graph2 are morphic, by recursion schemes
5.3 Second order
5.3.1 Second-order morphic words
5.3.2 Second-order scheme ω-frontiers
5.3.3 Liouville word
List of notations
Index
Bibliography
