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é:   
Parameterized synthesis of sequential transducers from rational relations over finite words
du groupe Séminaire Méthodes Formelles

Date 2019-04-02  11:00-12:00
TitreParameterized synthesis of sequential transducers from rational relations over finite words 
RésuméThe synthesis problem asks, given a specification that relates possible inputs to allowed outputs, whether there is a program realizing the specification, and if so, construct one. We consider synthesis of sequential transducers with synchronization parameters from rational relations over finite words. A sequential transducer is basically a deterministic finite automaton that outputs a finite word on each transition. A word relation can be represented by a set of synchronizations, called synchronization language. A synchronization of a pair of words is a single word where each position is annotated over {1,2}, which indicates whether it came from the input or output component, e.g., the synchronization (1a 2a 2b 1b 2a) represents the pair (ab,aba). The decision problems that have been studied so far either ask for synthesis by a synchronous sequential or by an arbitrary sequential transducer. We ask whether a sequential transducer whose allowed input/output behavior is specified by a given synchronization language can be synthesized from a given rational relation. The given synchronization language is referred to as synchronization parameter. Recently, main classes of rational relations have been characterized in terms of admissible synchronization languages, and we study the above problem for different combinations of classes of rational relations and classes of synchronization languages. The problem is undecidable in general, because it is known to be undecidable whether an arbitrary sequential transducer can be synthesized from a rational relation. For automatic relations (also called synchronized rational relations) it is known that it is decidable whether an arbitrary sequential transducer or a synchronous sequential transducer can be synthesized. Regarding our framework, the key contribution is that it is decidable whether a sequential transducer whose synchronization language lies within a given "automatic" synchronization language can be synthesized from an automatic relation. 
Lieu178 
OrateurSarah Winter 
UrlRWTH Aachen 



Aucun document lié à cet événement.

Retour
Retour à l'index