On time computability of functions in one-way cellular automata | Zendy

Thomas Buchholz | Zendy; Martin Kutrib | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On time computability of functions in one-way cellular automata

Author(s) -

Thomas Buchholz,

Martin Kutrib

Publication year - 1998

Publication title -

acta informatica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.481

H-Index - 40

eISSN - 1432-0525

pISSN - 0001-5903

DOI - 10.1007/s002360050123

Subject(s) - computability , computable function , theory of computation , bounded function , cellular automaton , constant (computer programming) , automaton , mathematics , realization (probability) , stochastic cellular automaton , model of computation , discrete mathematics , automata theory , computation , computer science , theoretical computer science , algorithm , programming language , mathematical analysis , statistics

. The capability of one-way (space-bounded) cellular automata (OCA) to time-compute functions is investigated. That means given a constant input of length a distinguished cell has to enter a distinguished state exactly after time steps. The family of such functions ((OCA)) is characterized in terms of formal language recognition. Several functions are proved to be time-computable and properties of (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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research