Distance desert automata and the star height problem
Distance desert automata and the star height problem
复制标题
距离沙漠自动机和星高问题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Kirsten
中科院分区：
文献类型：
--
作者：
D. Kirsten
我们证明，n 状态非确定性自动机接受的语言是否为星高一问题，在时间复杂度 (2^{2^{2^{O{(n)}}}}) 上是可判定的，这是星高一问题的第一个复杂性结果。为了实现这一目标，我们引入距离沙漠自动机作为距离自动机和沙漠自动机的联合推广，并通过解决潜在的 Burnside 问题来展示其有限性问题的可判定性。
We show that it is decidable in time complexity (2^{2^{2^{O{(n)}}}}) whether the language accepted by an n-state non-deterministic automaton is of star height one, which is the first ever complexity result for the star height one problem. To achieve this, we introduce distance desert automata as a joint generalization of distance automata and desert automata, and show the decidability of its limitedness problem by solving the underlying Burnside problem.