Multi-Buffer Simulations for Trace Language Inclusion

Milka Hutagalung
(Universität Kassel)
Norbert Hundeshagen
(Universität Kassel)
Dietrich Kuske
(Technische Universität Ilmenau)
Martin Lange
(Universität Kassel)
Etienne Lozes
(ENS Cachan)

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 several buffers before she executes them on her structure. We show that the simulation games are useful to approximate the inclusion of trace closures of languages accepted by finite-state automata, which is known to be undecidable. We study the decidability and complexity and show that the game with bounded buffers can be decided in polynomial time, whereas the game with one unbounded and one bounded buffer is highly undecidable. We also show some sufficient conditions on the automata for Duplicator to win the game (with unbounded buffers).

In Domenico Cantone and Giorgio Delzanno: Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2016), Catania, Italy, 14-16 September 2016, Electronic Proceedings in Theoretical Computer Science 226, pp. 213–227.
Published: 13th September 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.226.15 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org