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
