Loading...
Please wait, while we are loading the content...
Deterministic Turing Machines in the Range between Real-Time and Linear-Time (2000)
| Content Provider | CiteSeerX |
|---|---|
| Author | Klein, Andreas Klein, Andreas Kutrib, Martin Kutrib, Martin |
| Abstract | . Deterministic k-tape and multitape Turing machines with one-way, twoway 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 2 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. CR Subject Classification (1998): F.1.3, F.1.1, F.4.3 1 E-mail: andreas.klein@math.uni-giessen.de 2 E-mail: kutrib@informatik.uni-giessen.de Copyright c fl 2000 by the authors 1 Introduction When one is particularly interested in computations with small time bounds, lets say in the range between real-time and linear-time, most of the relevant Turing machine results have been published in the early times of computational complexity. In the sequel... |
| File Format | |
| Language | English |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Deterministic Turing Machine Time Bound Cr Subject Classification Multitape Turing Machine Computational Complexity Deterministic K-tape Class Weak Closure Property Separated Complexity Class Kutrib Informatik Infinite Time Hierarchy Several Type Separated Input Tape Small Time Bound Early Time Relevant Turing Machine Result Similar Result Sublinear Function |
| Content Type | Text |
| Resource Type | Technical Report |
