On time computability of functions in one-way cellular automata
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
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.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
Bericht / Arbeitsgruppe Informatik; 9502 / 1995