تقرير
Multi-Buffer Simulations for Trace Language Inclusion
| العنوان: | Multi-Buffer Simulations for Trace Language Inclusion |
|---|---|
| المؤلفون: | Hutagalung, Milka, Hundeshagen, Norbert, Kuske, Dietrich, Lange, Martin, Lozes, Etienne |
| المصدر: | EPTCS 226, 2016, pp. 213-227 |
| سنة النشر: | 2016 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Formal Languages and Automata Theory, Computer Science - Logic in Computer Science |
| الوصف: | We consider simulation games played between Spoiler and Duplicator on two B\"uchi 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). Comment: In Proceedings GandALF 2016, arXiv:1609.03648 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4204/EPTCS.226.15 |
| URL الوصول: | http://arxiv.org/abs/1609.04098 |
| رقم الأكسشن: | edsarx.1609.04098 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4204/EPTCS.226.15 |
|---|