📖
Synthesis of Data Word Transducers
Léo Exibard, Emmanuel Filiot, Pierre-Alain Reynier

Synthesis of Data Word Transducers

Science & Mathematics Published 2021 Verification Pending

Overview & Synopsis

In reactive synthesis, the goal is to automatically generate an implementation from a specification of the reactive and non-terminating input/output behaviours of a system. Specifications are usually modelled as logical formulae or automata over infinite sequences of signals (ω-words), while implementations are represented as transducers. In the classical setting, the set of signals is assumed to be finite. In this paper, we consider data ωwords instead, i.e., words over an infinite alphabet. In this context, we study specifications and implementations respectively given as automata and transducers extended with a finite set of registers. We consider different instances, depending on whether the specification is nondeterministic, universal or deterministic, and depending on whether the number of registers of the implementation is given or not. In the unbounded setting, we show undecidability for both universal and nondeterministic specifications, while decidability is recovered in the deterministic case. In the bounded setting, undecidability still holds for nondeterministic specifications, but can be recovered by disallowing tests over input data. The generic technique we use to show the latter result allows us to reprove some known result, namely decidability of bounded synthesis for universal specifications.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Synthesis of Data Word Transducers
Author / Organization Léo Exibard, Emmanuel Filiot, Pierre-Alain Reynier
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2021
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-88112
Original Source Link Visit Source Page on hal.science »