期刊名称：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
