Sujet de thèse: Higher-order pushdown automata with collapse

 

Directeurs de thèse : Igor Walukiewicz         

 

Courriels : igw@labri.fr         

 

Équipe: Méthodes Formelles

 

 

Description synthétique du sujet

 

Comprendre certains aspects d’implémentation de procédures récursifs de l'ordre supérieur. 

 

Description détaillée du sujet:

 

 

A celebrated result of Rabin says that the monadic second order (MSO) theory of the full infinite binary tree is decidable. From there it follows that MSO theory of any regular tree is decidable. One can think of a regular tree as a tree that is an unraveling of a finite graph, or equivalently, as the unraveling of the state graph of a finite automaton. Rabin's result has been generalized in several

way. For example, for push-down trees that are unravelings of graphs of configurations of push-down automata.

 

Regular trees and pushdown trees are two first levels of the hierarchy of higher-order pushdown automata. It was known for a long time that these automata correspond to so called safe recursive schemes. Recently, there was some important progress in understanding semantics of higher-order recursive program schemes when the safety assumption, that is rather technical, is removed.  It turns out that all higher-order schemes can be characterized by an extension of pushdown automata with a new stack operation called collapse. Still a fundamental open question remains: is the collapse operation necessary. If yes, the whole research programme about higher-order automata should be reconsidered for the extension. If no, we will get a huge advance in understanding of higher order recursion and its implementation.

The goal of this thesis will be to study collapsible higher-order pushdown automata and the associated languages.

 

 

Bibliography:

 

Matthew Hague, Andrzej S. Murawski, C.-H. Luke Ong, Olivier Serre:

Collapsible Pushdown Automata and Recursion Schemes. LICS 2008:

452-461

 

T. Knapik and D. Niwinski and P. Urzyczyn and I. Walukiewicz,

Unsafe grammars and panic automata, ICALP'05,  LNCS, Volume 3850, Pages:1450--1461, 2005