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
Document type :
Complete list of metadatas

Cited literature [83 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Wednesday, April 20, 2011 - 12:34:06 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Thursday, November 8, 2012 - 4:55:37 PM


Version validated by the jury (STAR)


  • HAL Id : tel-00587409, version 1


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



Record views


Files downloads