Skip to Main content Skip to Navigation

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 ε₀ 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 ε₀. 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 ω --- 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 metadata

Cited literature [83 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Wednesday, April 20, 2011 - 12:34:06 PM
Last modification on : Tuesday, May 18, 2021 - 7:56:13 AM
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⟩