Abstract
The chapter studies some families of signals generated by cellular automata and shows their application in cellular algorithms. As it does not seem to be possible to give a general definition of a signal, we choose, in this chapter, to think about signals as trajectories of information quanta. Various cellular automata that support propagation of the signals are discussed in the text. We develop a cellular automaton algorithm which implements transformations between various types of signals, namely the signals traveling rightwards are mapped to other type of signals. Then a cellular automaton is designed which builds an infinite family of right signals. Finally, connections between signals and grids, which are guidelines for cellular computations, are exposed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albert J. and Čulik K. A simple universal cellular automaton and its one-way totalistic version Complex Systems 1 (1987) 1–16.
Balzer R. An 8-states minimal time solution to the firing squad synchronization problem Information and Control 10 (1967) 22–42.
Berlekamp E., Conway V., Elwyn R. and Guy R. Winning Ways for Your Mathematical Plays. Vol 2 (Academic Press, 1982).
Boccara N., Nasser J. and Roger M. Particle-like structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular-automata rules. Physical Revue A 44 (1991) 866–875.
Choffrut, C. and Čulik, K. On real time cellular automata and trellis automata Acta Informaticae 21 (1991) 393–407.
Cole S. Real-time computation by n-dimensional iterative arrays of finite-state machine IEEE Trans. Comput. C-18 (1969) 349–365.
Delorme M. and Mazoyer J. Reconnaissance parallèle des langages rationnels sur automates cellulaires plans Theoretical Computer Science (2002)to appear.
Delorme M., Mazoyer J. and Tougne L. Discrete parabolas and circles on 2D cellular automata. Theoretical Computer Science 218 (1999) 347–417.
Durand B. and Róka Zs. The Game of Life: universality revisited. In: M. Delorme and J. Mazoyer (Editors) Cellular Automata: A Parallel Model (Kluwer, 1999) 51–76.
Fisher P. Generation of primes by a one dimensional real time iterative array Journal of the ACM 12 (1965) 388–394.
Ibarra O. Computational complexity of cellular automata: an overview In: M. Delorme and J. Mazoyer (Editors) Cellular Automata: A Parallel Model (Kluwer, 1999) 181–198.
Martin B. A goup interpretation of particles generated by one dimensional cellular automaton, 54 Wolfram’s rule Int. Journ. of Mod. Phys. C. 11–1 (2000) 101–123.
Mazoyer J. A six states minimal time solution to the Firing Squad Synchronization Problem Theoretical Computer Science 50 (1987) 183–238.
Mazoyer J. Computations on one-dimensional cellular automata Annals of Mathematics and Artificial Intelligence 16 (1996) 285–309.
Mazoyer J. Computations on grids In: M. Delorme and J. Mazoyer (Editors) Cellular Automata: A Parallel Model (Kluwer, 1999) 119–149.
Mazoyer J. and Rapaport I. Inducing an order on cellular automata by a grouping operation Discrete Applied Mathematics 91 (1999) 177–196.
Mazoyer J. and Terrier V. Signals in one dimensional cellular automata Theoretical Computer Science 217 (1999) 53–80.
Mazoyer J., Nichitiu C. and Rémila E. Algorithms for leader election by cellular automata to appear in Journal of Algorithms (2001).
Ollinger N. Towards an Algorithmic Classification of Cellular Automata. Research report, 2001–10, LIP, Ecole Normale Supérieure de Lyon, 2001.
Róka Zs. Automates cellulaires sur graphes de Cayley. Ph.D Thesis, Ecole Normale Supérieure de Lyon, 1994.
Smith A. A simple computation-universal space Journal of ACM 18 (1971) 339–353.
Waksman A. An optimum solution to the firing squad synchronization problem Information and Control 9 (1966) 66–78.
Willson S. Cellular automata can generate fractals Discrete Applied Mathematics 8 (1984) 91–99.
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag London
About this chapter
Cite this chapter
Delorme, M., Mazoyer, J. (2002). Signals on Cellular Automata. In: Adamatzky, A. (eds) Collision-Based Computing. Springer, London. https://doi.org/10.1007/978-1-4471-0129-1_9
Download citation
DOI: https://doi.org/10.1007/978-1-4471-0129-1_9
Publisher Name: Springer, London
Print ISBN: 978-1-85233-540-3
Online ISBN: 978-1-4471-0129-1
eBook Packages: Springer Book Archive