Evènement pour le groupe
Graphes et Logique
Date | 2012-03-13 11:00-12:00 |
Titre | MSO+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. |
Lieu | salle 76 |
Orateur | Michał Skrzypczak |
Email | mskrzypczak@mimuw.edu.pl |
Url | University of Warsaw |
Aucun document lié à cet événement.
RetourRetour à l'index