Two-Buffer Simulation Games
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 us...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2016-07-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1608.00654v1 |
| _version_ | 1818700562899664896 |
|---|---|
| author | Milka Hutagalung Norbert Hundeshagen Dietrich Kuske Martin Lange Etienne Lozes |
| author_facet | Milka Hutagalung Norbert Hundeshagen Dietrich Kuske Martin Lange Etienne Lozes |
| author_sort | Milka Hutagalung |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-17T15:06:56Z |
| format | Article |
| id | doaj.art-6366ae6d732242a683ef5ba5268beb84 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-17T15:06:56Z |
| publishDate | 2016-07-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-6366ae6d732242a683ef5ba5268beb842022-12-21T21:43:47ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802016-07-01220Proc. Cassting 2016/SynCoP'16273810.4204/EPTCS.220.3:2Two-Buffer Simulation GamesMilka Hutagalung0Norbert Hundeshagen1Dietrich Kuske2Martin Lange3Etienne Lozes4 University of Kassel, Germany University of Kassel, Germany Technische Universität Ilmenau, Germany University of Kassel, Germany 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.http://arxiv.org/pdf/1608.00654v1 |
| spellingShingle | Milka Hutagalung Norbert Hundeshagen Dietrich Kuske Martin Lange Etienne Lozes Two-Buffer Simulation Games Electronic Proceedings in Theoretical Computer Science |
| title | Two-Buffer Simulation Games |
| title_full | Two-Buffer Simulation Games |
| title_fullStr | Two-Buffer Simulation Games |
| title_full_unstemmed | Two-Buffer Simulation Games |
| title_short | Two-Buffer Simulation Games |
| title_sort | two buffer simulation games |
| url | http://arxiv.org/pdf/1608.00654v1 |
| work_keys_str_mv | AT milkahutagalung twobuffersimulationgames AT norberthundeshagen twobuffersimulationgames AT dietrichkuske twobuffersimulationgames AT martinlange twobuffersimulationgames AT etiennelozes twobuffersimulationgames |