Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-075 | 7th September 2000 00:00

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

RSS-Feed




TR00-075
Authors: Andreas Klein, Martin Kutrib
Publication: 18th September 2000 09:04
Downloads: 1026
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint