Evènement pour le groupe Graphes et Logique

Date 2012-03-13  11:00-12:00
TitreMSO+U defines languages at arbitrarily high levels of the projective hierarchy 
RésuméThis work shows that for each i ∈ N there exists a ω-word language H_i definable in Monadic Second Order Logic extended with the unbounding quantifier (MSO + U) such that H_i is hard for i'th level of the projective hierarchy. Since it is not hard to see that each language expressible in MSO + U is projective, our finding solves the topological complexity of MSO + U. The result can immediately be transferred from ω-words to infinite labelled trees. As a consequence of the topological hardness we note that no alternating automaton with a Borel acceptance condition — or even with an acceptance condition of a bounded projective complexity — can capture all of MSO + U.  
Lieusalle 76 
OrateurMichał Skrzypczak 
UrlUniversity of Warsaw 

Aucun document lié à cet événement.

Retour à l'index