Journées Nationales Informatique Mathématique 2019
11-14 mars 2019 Orléans (France)
Reactive Synthesis of Systems over Data Words
Léo Exibard  1, 2@  , Pierre-Alain Reynier  1  , Emmanuel Filiot  3  
1 : Laboratoire dÍnformatique et Systèmes
Aix Marseille Université : UMR7020, Université de Toulon : UMR7020, Centre National de la Recherche Scientifique : UMR7020
2 : Université libre de Bruxelles, MFV
3 : Université libre de Bruxelles, MFV

The transducer synthesis problem asks, given a specification S, where S is a relation over I x O (I and O are sets of infinite words), whether there exists an implementation f: I --> O which:
(1) fulfils the specification, i.e., (i,f(i)) € S for all i € I, and
(2) can be defined by some input-deterministic (aka sequential) transducer T_f. If such an implementation f exists, the procedure should also output T_f.
This problem has been well studied, both when S is expressed with a logic (e.g. MSO, LTL), and when S is itself given as a (nondeterministic, finite-valued,... a priori non sequential) transducer.

Here, we extend this problem to words over an infinite alphabet, namely data words. S is given as a register automaton, ie a finite automaton equipped with registers it can use to store and output data. We target implementations expressed as sequential register transducers, a notion we define analogously to the finite case. We consider different instances, depending on whether the specification is nondeterministic, universal or deterministic and introduce the notion of ``test-free'' register automaton to recover decidability in the nondeterministic case.


Personnes connectées : 1