The structure of orders in the pushdown hierarchy

Abstract : 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
Keywords :
Document type :
Theses

Cited literature [83 references]

https://pastel.archives-ouvertes.fr/tel-00587409
Contributor : Abes Star :  Contact
Submitted on : Wednesday, April 20, 2011 - 12:34:06 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Thursday, November 8, 2012 - 4:55:37 PM

File

TH2010PEST1009_diffusion.pdf
Version validated by the jury (STAR)

Identifiers

• HAL Id : tel-00587409, version 1

Citation

Laurent Braud. The structure of orders in the pushdown hierarchy. Modeling and Simulation. Université Paris-Est, 2010. English. ⟨NNT : 2010PEST1009⟩. ⟨tel-00587409⟩

Record views