Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Below linear-time : Dimensions versus time

Kutrib, Martin


Zum Volltext im pdf-Format: Dokument 1.pdf (291 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-6112
URL: http://geb.uni-giessen.de/geb/volltexte/2001/611/


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
Zeitschrift, Serie: IFIG Research Report ; 0005 / 2000
Sprache: Englisch
Erstellungsjahr: 2000
Publikationsdatum: 08.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

Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand