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é:   
Walking in the free inverse monoid
du groupe Graphes et Logique

Date 2012-10-02  11:00-12:00
TitreWalking in the free inverse monoid 
RésuméWe consider subsets of the free inverse monoid or, following Munn's representation theorem, languages of finite birooted trees. We propose three notions of definability for these languages: definability by means of finite state walking automata with nested (invisible) pebbles, definability by means of (extension of) Kleene regular expressions, and definability by means of (adequate) premorphisms (or relational morphisms) in (adequate) finite ordered monoids. Various correspondences, linking these three notions together, are shown to hold. Finite walking automata with a finite number of pebbles are shown to be captured by regular expressions; the number of allowed pebbles corresponds to the nesting depth of a projection operator onto languages of idempotent birooted trees. Finite walking automata with a finite or an infinite number of pebbles are also shown to be captured by finitely generated premorphisms from the (naturally ordered) free inverse monoid in their associated (finite) transition monoids (ordered by inclusion). These results strengthen the idea that the category of (quasi-inverse) ordered monoids and (appropriate) premorphisms is an adequate framework for the study of walking automata on trees much in the same way the category of monoids and morphisms is an adequate framework for the study of classic (one way) automata. Moreover, since our algebraic characterization of walking automata holds even for automata using infinitely many pebbles, it also provides a presumably new algebraic framework for the study of regular languages of finite trees. This work extend a similar work on languages of one-dimensional tiles (linear unidirectional birooted trees) recently done with Anne Dicky. 
LieuSalle 076 
OrateurDavid Janin 
Emaildavid.janin@labri.fr 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index