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/611/


Below linear-time : Dimensions versus time

Kutrib, Martin


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

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Deutsch): linear-time
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 ; 0005 / 2000
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum: 09.02.2001
Kurzfassung auf Englisch: Deterministic d-dimensional Turing machines are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form id + r where r E o(id) is a sublinear function. It is shown that for any dimension d >= 1 there exist infinite time hierarchies of separated complexity classes in that range. Moreover, for the corresponding time bounds separated dimension hierarchies are proved.



CR Subject Classification (1998): F.1.3, F.1.1, F.4.3