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é:   
Algebras, automata and logic for languages of labeled birooted trees
du groupe Graphes et Logique

Date 2013-03-26  11:00-12:00
TitreAlgebras, automata and logic for languages of labeled birooted trees 
RésuméWe study languages of labeled finite birooted trees: Munn’s birooted trees extended with vertex labeling. We define a notion of finite state birooted tree automata that is shown to capture the class of languages that are upward closed w.r.t. the natural order and definable in Monadic Second Order Logic. Then, relying on the inverse monoid structure of labeled birooted trees, we derive a notion of recognizable languages by means of (adequate) premorphisms into finite (adequately) ordered monoids. This notion is shown to capture finite boolean combinations of languages as above. As a particular case, a simple encoding of finite (mono-rooted) labeled trees in an antichain of labeled birooted trees shows that classical regular languages of finite (mono-rooted) trees are also recognized by such premorphisms and finite ordered monoids. 
LieuSalle 076 
OrateurDavid Janin 
Emaildavid.janin@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index