Below linear-time : Dimensions versus time
| dc.contributor.author | Kutrib, Martin | |
| dc.date.accessioned | 2022-09-12T09:38:48Z | |
| dc.date.available | 2001-02-08T23:00:00Z | |
| dc.date.available | 2022-09-12T09:38:48Z | |
| dc.date.issued | 2000 | |
| dc.description.abstract | 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 | en |
| dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-6112 | |
| dc.identifier.uri | https://jlupub.ub.uni-giessen.de//handle/jlupub/7576 | |
| dc.identifier.uri | http://dx.doi.org/10.22029/jlupub-7010 | |
| dc.language.iso | en | de_DE |
| dc.relation.ispartofseries | IFIG Research Report; 0005 / 2000 | |
| dc.rights | In Copyright | * |
| dc.rights.uri | http://rightsstatements.org/page/InC/1.0/ | * |
| dc.subject | linear-time | de_DE |
| dc.subject.ddc | ddc:004 | de_DE |
| dc.title | Below linear-time : Dimensions versus time | en |
| dc.type | workingPaper | de_DE |
| local.affiliation | FB 07 - Mathematik und Informatik, Physik, Geographie | de_DE |
| local.opus.fachgebiet | Informatik | de_DE |
| local.opus.id | 611 | |
| local.opus.institute | Institut für Informatik | de_DE |
Dateien
Originalbündel
1 - 1 von 1