Multi-buffer simulations: Decidability and complexity
Multi-buffer simulations: Decidability and complexity
复制标题
多缓冲区模拟：可判定性和复杂性
DOI：
10.1016/j.ic.2018.09.008
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
E. Lozes
中科院分区：
文献类型：
--
作者：
M. Hutagalung;N. Hundeshagen;D. Kuske;M. Lange;E. Lozes
多缓冲区模拟是两个非确定性 Büchi 自动机 (NBA) 之间公平模拟的改进。它的特点是游戏中的字母被推入有界或无界容量的 FIFO 缓冲区并从中取出。具有单个缓冲区的游戏近似于 NBA 的 PSPACE 完整语言包含问题。通过多个缓冲区和字母到缓冲区的固定映射，这些游戏近似了 Mazurkiewicz 跟踪语言之间的不可判定包含问题。我们研究了多缓冲区模拟的可判定性和复杂性，并获得了以下结果：固定有界缓冲区的 P 完整性、单个无界缓冲区情况下的 EXPTIME 完整性以及两个缓冲区（其中至少一个是无界）的高不可判定性（在分析层次结构中）。我们还考虑了一种变体，其中缓冲区保持不变或刷新，并显示单缓冲区情况的 PSPACE 完整性。
Multi-buffer simulation is a refinement of fair simulation between two nondeterministic Büchi automata (NBA). It is characterised by a game in which letters get pushed to and taken from FIFO buffers of bounded or unbounded capacity.Games with a single buffer approximate the PSPACE-complete language inclusion problem for NBA. With multiple buffers and a fixed mapping of letters to buffers these games approximate the undecidable inclusion problem between Mazurkiewicz trace languages.We study the decidability and complexity of multi-buffer simulations and obtain the following results: P-completeness for fixed bounded buffers, EXPTIME-completeness in case of a single unbounded buffer and high undecidability (in the analytic hierarchy) with two buffers of which at least one is unbounded. We also consider a variant in which the buffers are kept untouched or flushed and show PSPACE-completeness for the single-buffer case.
登录
查看更多内容
有理跟踪语言的“最后”决策问题
DOI：
--
发表时间：
1992
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
J. Sakarovitch
通讯作者：
J. Sakarovitch
递归函数理论和有效可计算性（1967 年重印）
DOI：
--
发表时间：
1987
期刊：
影响因子：
--
作者：
H. Rogers
通讯作者：
H. Rogers
二缓冲模拟游戏
DOI：
--
发表时间：
2016
期刊：
Cassting/SynCoP
影响因子：
--
作者：
M. Hutagalung;Norbert Hundeshagen;D. Kuske;M. Lange;É. Lozes
通讯作者：
É. Lozes
Büchi Automata 的缓冲模拟游戏
DOI：
--
发表时间：
2014
期刊：
International Conference on Automata and Formal Languages
影响因子：
--
作者：
M. Hutagalung;M. Lange;É. Lozes
通讯作者：
É. Lozes
DOI：
10.1145/4904.4993
发表时间：
1986-01
期刊：
J. ACM
影响因子：
--
作者：
D. Harel
通讯作者：
D. Harel