Selected publications at LSV: 2006

Abstract:
We study the synthesis problem for external linear or branching specifications and distributed, synchronous architectures with arbitrary delays on processes. External means that the specification only relates input and output variables. We introduce the subclass of uniformly well-connected (UWC) architectures for which there exists a routing allowing each output process to get the values of all inputs it is connected to, as soon as possible. We prove that the distributed synthesis problem is decidable on UWC architectures if and only if the set of all sets of input variables visible by output variables is totally ordered, under set inclusion. We also show that if we extend this class by letting the routing depend on the output process, then the previous decidability result fails. Finally, we provide a natural restriction on specifications under which the whole class of UWC architectures is decidable.

@inproceedings{GSZ-fsttcs2006,
   address = {Kolkata, India},
   author = {Gastin, Paul and Sznajder, Nathalie and Zeitoun, Marc},
   booktitle = {{P}roceedings of the 26th {C}onference on {F}oundations of {S}oftware {T}echnology and {T}heoretical {C}omputer {S}cience ({FSTTCS}'06)},
   DOI = {10.1007/11944836_30},
   editor = {Garg, Naveen and Arun-Kumar, S.},
   month = dec,
   pages = {321-332},
   publisher = {Springer},
   series = {Lecture Notes in Computer Science},
   title = {Distributed synthesis for well-connected architectures},
   url = {http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/GSZ-fsttcs2006.pdf},
   volume = {4337},
   year = {2006},
}

About LSV