文章基本信息

标题：Deterministic Turing Machines in the Range between Real-Time and Linear-Time
本地全文：下载
作者：Andreas Klein, Martin Kutrib
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Deterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n+r(n) where r in o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. For these classes weak closure properties are proved. Finally, it is shown that similar results are valid for several types of acceptors with the same time bounds.
关键词：Keywords: automata, closure properties, Computational Complexity, fast computations, time hierarchies, Turing machines