Zur Kurzanzeige

dc.contributor.authorKutrib, Martin
dc.date.accessioned2022-09-12T09:38:48Z
dc.date.available2001-02-08T23:00:00Z
dc.date.available2022-09-12T09:38:48Z
dc.date.issued2000
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-6112
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7576
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-7010
dc.description.abstractDeterministic 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.3en
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 0005 / 2000
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectlinear-timede_DE
dc.subject.ddcddc:004de_DE
dc.titleBelow linear-time : Dimensions versus timeen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.id611
local.opus.instituteInstitut für Informatikde_DE
local.opus.fachgebietInformatikde_DE


Dateien zu dieser Ressource

Thumbnail

Das Dokument erscheint in:

Zur Kurzanzeige

Urheberrechtlich geschützt