Evolving Computability - 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015. Proceedings
Evolving Computability - 11th Conference on Computability in Europe, CiE 2015, Bucharest, Romania, June 29-July 3, 2015. Proceedings
复制标题
不断发展的可计算性 - 第 11 届欧洲可计算性会议，CiE 2015，罗马尼亚布加勒斯特，2015 年 6 月 29 日至 7 月 3 日。会议记录
DOI：
10.1007/978-3-319-20028-6_21
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Halava V
中科院分区：
文献类型：
--
作者：
Halava V
本文致力于研究几种具有可达性目标的无限状态攻击者-防御者博弈。我们证明了在几种低维数学游戏（包括向量可达性游戏、文字游戏和辫子游戏）中检查获胜策略是否存在的不可判定性。为了证明这些结果，我们考虑对无限字进行操作的加权自动机模型，并证明对于这种新型加权自动机来说，普遍性问题是不可判定的。我们通过使用无限邮政对应问题的非标准编码来证明普遍性问题是不可判定的。
The paper is devoted to several infinite-state Attacker–Defender games with reachability objectives. We prove the undecidability of checking for the existence of a winning strategy in several low-dimensional mathematical games including vector reachability games, word games and braid games. To prove these results, we consider a model of weighted automata operating on infinite words and prove that the universality problem is undecidable for this new class of weighted automata. We show that the universality problem is undecidable by using a non-standard encoding of the infinite Post correspondence problem.