𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Linear speed-up for cellular automata synchronizers and applications

✍ Scribed by Olivier Heen

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
816 KB
Volume
188
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Simple cellular automata can be used as language recognizers or function calculators. There exist several proofs of the linear speed-up theorem in strong form for rccognizers [7,6, 1 l] but not for calculators. In this paper we design a linear speed-up method for a special kind of calculators, namely the synchronizers, which are diKcrent from recognizers.

As a consequence, we extend a result from J. Mazoyer by proving that any polynomial with rational coefficients of a synchronization time is also a synchronization time (provided that it be greater than a certain minimal time).

πŸ“œ SIMILAR VOLUMES

Efficient constant speed-up for one dime
Efficient constant speed-up for one dimensional cellular automata calculators
✍ Olivier Heen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 558 KB

One-dimensional cellular automata (CA) can be used as function calculators: starting from an input word, an output configuration is reached, where the result is written on all cells. The constant speed-up theorem for this model was first established by C. Choffrut and K. Culik, but an exponential gr

Ergodicity, transitivity, and regularity
Ergodicity, transitivity, and regularity for linear cellular automata over Zm
✍ Gianpiero Cattaneo; Enrico Formenti; Giovanni Manzini; Luciano Margara πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 142 KB

We study the dynamical behavior of D-dimensional linear cellular automata over Zm. We provide an easy-to-check necessary and su cient condition for a D-dimensional linear cellular automata over Z m to be ergodic and topologically transitive. As a byproduct, we get that for linear cellular automata e

A decision procedure for well-formed lin
A decision procedure for well-formed linear quantum cellular automata
✍ Christoph DΓΌrr; Huong LΓͺThanh; Miklos Santha πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 196 KB

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. W