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é:   
Closure properties of synchronized relations
du groupe Séminaire Méthodes Formelles

Date 2018-09-25  11:00-12:00
TitreClosure properties of synchronized relations 
RésuméA standard approach to define k-ary word relations over a finite alphabet A is through k-tape finite state automata that recognize regular languages L over {1, ... , k} x A, where (i,a) is interpreted as reading letter a from tape i. Accordingly, a word w in L denotes the tuple (u_1, ... , u_k) of words over A in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of Rational relations, enforcing restrictions on the reading regime from the tapes, which we call "synchronization", yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language L onto {1, ... , k}. In this way, for each regular language C over the alphabet {1, ... , k}, one obtains a class Rel(C) of relations. Synchronous, Recognizable, and Length-preserving rational relations are all examples of classes that can be defined in this way. We study basic properties of these classes of relations, in terms of closure under intersection, complement, concatenation, Kleene star and projection. In each case we characterize the classes with the property through a decidable property. 
Lieu178 
OrateurMaría Emilia Descotte 
Emailhttp://www.labri.fr/perso/mdescotte/ 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index