Evènement pour le groupe Séminaire Méthodes Formelles

Date 2018-06-12  11:00-12:00
TitreUndecidability of MSO+“ultimately periodic” 
RésuméWe prove that MSO on omega-words becomes undecidable if allowing to quantify over sets of positions that are ultimately periodic, i.e., sets X such that for some positive integer p, ultimately either both or none of positions x and x+p belong to X. We obtain it as a corollary of the undecidability of MSO on omega-words extended with the second-order predicate U1(X) which says that the distance between consecutive positions in a set X of naturals is unbounded. This is achieved by showing that adding U1 to MSO gives a logic with the same expressive power as MSO+U, a logic on omega-words with undecidable satisfiability. This is joint work with Mikolaj Bojanczyk, Laure Daviaud, Vincent Penelle and Sreejith. 
OrateurBruno Guillon 
UrlUniversity of Milan 

Aucun document lié à cet événement.

Retour à l'index