On the power of one-way bounded cellular time computers
| dc.contributor.author | Buchholz, Thomas | |
| dc.contributor.author | Kutrib, Martin | |
| dc.date.accessioned | 2022-06-30T20:11:39Z | |
| dc.date.available | 1998-06-22T22:00:00Z | |
| dc.date.issued | 1996 | |
| dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-225 | |
| dc.identifier.uri | https://jlupub.ub.uni-giessen.de//handle/jlupub/2216 | |
| dc.identifier.uri | http://dx.doi.org/10.22029/jlupub-1986 | |
| dc.description.abstract | Comparisons of different cellular devices and the investigation of their computing power can be made in terms of their capabilities to timeconstruct and timecompute functions. Timeconstruction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas timecomputation requires the distinguished cell to enter a distinguished state firstly at time step f(n), where n is the length of the input. Here the family of functions which are timeconstructible by a twoway unbounded cellular space (F(CS)) is characterized in terms of functions which are timecomputable by one of the simplest cellular devices, a oneway bounded cellular automaton (C (OCA)). Conceptually, timeconstructible functions have to be strictly increasing. Regarding that restriction the reverse characterization is shown, too. Some results concerning the structure of F(CS) and C(OCA) and their relation to formal language recognition are established. | en |
| dc.language.iso | en | de_DE |
| dc.relation.ispartofseries | Bericht / Arbeitsgruppe Informatik; 9604 / 1996 | |
| dc.rights | In Copyright | * |
| dc.rights.uri | http://rightsstatements.org/page/InC/1.0/ | * |
| dc.subject.ddc | ddc:004 | de_DE |
| dc.title | On the power of one-way bounded cellular time computers | en |
| dc.type | workingPaper | de_DE |
| local.affiliation | FB 07 - Mathematik und Informatik, Physik, Geographie | de_DE |
| local.opus.id | 22 | |
| local.opus.institute | Arbeitsgruppe Informatik | de_DE |
| local.opus.fachgebiet | Informatik | de_DE |
Dateien zu dieser Ressource
Das Dokument erscheint in:
Urheberrechtlich geschützt