On time computability of functions in one-way cellular automata
| dc.contributor.author | Buchholz, Thomas | |
| dc.contributor.author | Kutrib, Martin | |
| dc.date.accessioned | 2022-06-30T20:11:38Z | |
| dc.date.available | 1998-05-25T22:00:00Z | |
| dc.date.issued | 1995 | |
| dc.description.abstract | The capability of oneway (spacebounded) cellular automata (OCA) to timecompute functions is investigated. That means given an constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C (OCA)) is characterized in terms of formal language recognition. Several functions are proved to be timecomputable and properties of C(OCA) are given. The timecomputation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time. | en |
| dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-189 | |
| dc.identifier.uri | https://jlupub.ub.uni-giessen.de//handle/jlupub/2212 | |
| dc.identifier.uri | http://dx.doi.org/10.22029/jlupub-1982 | |
| dc.language.iso | en | de_DE |
| dc.relation.ispartofseries | Bericht / Arbeitsgruppe Informatik; 9502 / 1995 | |
| dc.rights | In Copyright | * |
| dc.rights.uri | http://rightsstatements.org/page/InC/1.0/ | * |
| dc.subject.ddc | ddc:004 | de_DE |
| dc.title | On time computability of functions in one-way cellular automata | 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 | 18 | |
| local.opus.institute | Arbeitsgruppe Informatik | de_DE |
Dateien
Originalbündel
1 - 1 von 1