Two-Buffer Simulation Games

Milka Hutagalung
(University of Kassel, Germany) 		Norbert Hundeshagen
(University of Kassel, Germany) 		Dietrich Kuske
(Technische Universität Ilmenau, Germany) 		Martin Lange
(University of Kassel, Germany) 		Etienne Lozes
(LSV, ENS Cachan & CNRS, France)

We consider simulation games played between Spoiler and Duplicator on two Büchi automata in which the choices made by Spoiler can be buffered by Duplicator in two different buffers before she executes them on her structure. Previous work on such games using a single buffer has shown that they are useful to approximate language inclusion problems. We study the decidability and complexity and show that games with two buffers can be used to approximate corresponding problems on finite transducers, i.e. the inclusion problem for rational relations over infinite words.

In Thomas Brihaye, Benoît Delahaye, Loïg Jezequel, Nicolas Markey and Jiří Srba: Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16), Eindhoven, The Netherlands, April 2-3, 2016, Electronic Proceedings in Theoretical Computer Science 220, pp. 27–38.
Published: 31st July 2016.
ArXived at: https://dx.doi.org/10.4204/EPTCS.220.3 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org