Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Undecidability of MSO+“ultimately periodic”
du 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. 
Lieu178 
OrateurBruno Guillon 
Emailhttp://guillon.di.unimi.it/ 
UrlUniversity of Milan 



Aucun document lié à cet événement.

Retour
Retour à l'index