Dear users, we have given JLUpub a major update, unfortunately there are currently still some minor problems. If you encounter any errors, we ask for your understanding and are grateful for any hints at https://jlupub.ub.uni-giessen.de/info/feedback.
 

On time computability of functions in one-way cellular automata

Datum

1995

Betreuer/Gutachter

Weitere Beteiligte

Herausgeber

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Zusammenfassung

The capability of one­way (space­bounded) cellular automata (OCA) to time­compute 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 time­computable and properties of C(OCA) are given. The time­computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.

Beschreibung

Inhaltsverzeichnis

Anmerkungen

Erstpublikation in

Sammelband

URI der Erstpublikation

Forschungsdaten

Schriftenreihe

Bericht / Arbeitsgruppe Informatik; 9502 / 1995

Erstpublikation in

Zitierform