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

Date 2018-10-02  11:00-12:00
TitreLanguages over countable linear orderings 
RésuméWe look at words which are mappings from a countable linear ordering to a finite alphabet. Finite words, Omega words etc satisfy the above condition. We will also look at other kind of words. In this talk, we study the languages (of words) definable by different logics. We consider first order logic, weak monadic second order logic, two variable fragments and a host of other logics. We are interested in the relationship between these logics. Are these logics expressively different? We will show that all these logics can be characterized by an algebraic structure called o-algebra and its subclasses. This helps us compare the respective expressive power of these logics. Moreover, since there is an effective translation to o-algebras from formulas, we have decidability for the satisfiability problem. 
OrateurA. V. Sreejith 
UrlIIT Goa 

Aucun document lié à cet événement.

Retour à l'index