Buffered Simulation Games for Büchi Automata
Buffered Simulation Games for Büchi Automata
复制标题
Büchi Automata 的缓冲模拟游戏
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
É. Lozes
中科院分区：
文献类型：
--
作者：
M. Hutagalung;M. Lange;É. Lozes
我们介绍了缓冲模拟，这是一组比标准模拟更接近语言包含的模拟关系。缓冲模拟是基于一个双人游戏，在这个游戏中，第二个玩家（这里称为复制者）可能会跳过他的回合，并在游戏的下一轮中对给定的移动做出反应。我们考虑了这些缓冲模拟的各种变体，并建立了它们的可判定性和精确复杂性。
We introduce buffered simulations, a family of simulation relations that better approximate language inclusion than standard simulations. Buffered simulations are based on a two-player game in which the second player, called here Duplicator, may skip his turn and respond to a given move in a later round of the game. We consider various variants of these buffered simulations and es- tablish their decidability and exact complexity.