Complexity of multi-head finite automata: Origins and directions
Complexity of multi-head finite automata: Origins and directions
复制标题
多头有限自动机的复杂性：起源和方向
DOI：
10.1016/j.tcs.2010.08.024
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Andreas Malcher
中科院分区：
文献类型：
--
作者：
M. Holzer;Martin Kutrib;Andreas Malcher
多头有限自动机首先由Rabin和Scott在1964年以及Rosenberg在1966年提出并研究。从那时起，大量文献的计算和计算复杂性问题的多头有限自动机记录这些设备的重要性已经开发。虽然多头有限自动机是一个简单的概念，但它们的计算行为可能已经非常复杂，并导致这些设备上的不可判定甚至不可半判定的问题，例如空性，有限性，普遍性，等价性等。此外，不同类型的多头有限自动机之间的转换在大多数情况下会导致无法由任何递归函数约束的大小界限，所谓的非递归权衡。这些强烈的负面结果引发了研究的子类和替代表征的多头有限自动机，更好地了解非递归权衡的性质，因此，可判定和不可判定的问题之间的边界。在本文中，我们游览了这一文献的一个片段。
Multi-head finite automata were introduced and first investigated by Rabin and Scott in 1964 and Rosenberg in 1966. Since that time, a vast literature on computational and descriptional complexity issues on multi-head finite automata documenting the importance of these devices has been developed. Although multi-head finite automata are a simple concept, their computational behavior can be already very complex and leads to undecidable or even non-semi-decidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. Additionally the conversions between different types of multi-head finite automata induce in most cases size bounds that cannot be bounded by any recursive function, so-called non-recursive trade-offs. These strong negative results trigger the study of subclasses and alternative characterizations of multi-head finite automata for a better understanding of the nature of non-recursive trade-offs and, thus, the borderline between decidable and undecidable problems. In the present paper, we tour a fragment of this literature.