Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://geb.uni-giessen.de/geb/volltexte/2001/608/


Deterministic Turing machines in the range between real-time and linear-time

Klein, Andreas ; Kutrib, Martin


pdf-Format: Dokument 1.pdf (401 KB)
ps gepackt: class="frontdoor">Dokument1.gz (210 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Deutsch): Deterministic turing machine
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper (Forschungsbericht, Arbeitspapier)
Zeitschrift, Serie: IFIG Research Report ; 0002 / 2000
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum: 08.02.2001
Kurzfassung auf Englisch: 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 E 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