Two-Buffer Simulation Games
Two-Buffer Simulation Games
复制标题
二缓冲模拟游戏
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
É. Lozes
中科院分区：
文献类型：
--
作者：
M. Hutagalung;Norbert Hundeshagen;D. Kuske;M. Lange;É. Lozes
我们考虑在两个Buchi自动机上进行的剧透者和复制者之间的模拟游戏，其中剧透者做出的选择可以在她在自己的结构上执行之前被复制者缓冲在两个不同的缓冲区中。之前对这类游戏使用单一缓冲区的研究表明，它们对近似语言包含问题很有用。我们研究了具有两个缓冲区的对策的可决性和复杂性，并证明了具有两个缓冲区的对策可以用来近似有限换能器上的相应问题，即无限词上有理关系的包含问题。
We consider simulation games played between Spoiler and Duplicator on two Buchi 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.