✦ LIBER ✦
Efficient constant speed-up for one dimensional cellular automata calculators
✍ Scribed by Olivier Heen
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 558 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0167-8191
No coin nor oath required. For personal study only.
✦ Synopsis
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 growth of the set of state was required. We design a new method necessitating only a polynomial growth. Moreover, the product states appear very sparsely in the space-time diagram of the accelerated device. We also give hints for generalizing the method to CA with wide neighborhood. 0 1997 Elsevier Science B.V.