Characterization of 1-d periodic boundary reversible CA. (English) Zbl 1338.68179
de Oliveira, Pedro P. B. (ed.) et al., Proceedings of the 15th international workshop on cellular automata and discrete complex systems, São Paulo, Brazil, October 10–12, 2009. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 252, 205-227 (2009).
Summary: This paper reports characterization of one dimensional 3-neighborhood periodic boundary cellular automata (CA). It targets characterization of CA rules for efficient synthesis of reversible CA. The concept of reachability tree, as it has been proposed in [the first author et al., “Design of nonlinear CA based TPG without prohibited pattern set in linear time”, J. Electron. Test. 21, No. 1, 95–107 (2005); the authors, Lect. Notes Comput. Sci. 4173, 68–77 (2006; Zbl 1155.68458); the first author et al., Lect. Notes Comput. Sci. 3305, 813–822 (2004; Zbl 1116.68509)], is redefined to classify the CA rules that can form a reversible CA. Such classification also enables synthesis of a reversible periodic boundary CA in linear time.
For the entire collection see [Zbl 1281.68041].
For the entire collection see [Zbl 1281.68041].
MSC:
| 68Q80 | Cellular automata (computational aspects) |
Keywords:
non-uniform cellular automata; reversible CA; reachability tree; periodic boundary; rule classReferences:
| [1] | Amoroso, S.; Patt, Y. N., Decision procedures for surjectivity injectivity of parallel maps for tesselation structures, Journal of Computer and System Sciences, 6, 448-464 (1972) · Zbl 0263.94019 |
| [2] | P. H. Bardell. Analysis of Cellular Automata Used as Pseudo-random Pattern Generators. In Proceedings of International Test Conference, pages 762-768, 1990; P. H. Bardell. Analysis of Cellular Automata Used as Pseudo-random Pattern Generators. In Proceedings of International Test Conference, pages 762-768, 1990 |
| [3] | Kevin Cattel and J, Muzio., C. Synthesis of One Dimensional Linear Hybrid Cellular Automata, IEEE Trans. on CAD, 15, 325-335 (1996) |
| [4] | Chaudhuri, P. Pal; Chowdhury, D. Roy; Nandi, S.; Chatterjee, S., Additive Cellular Automata - Theory and Applications, volume 1 (1997), IEEE Computer Society Press: IEEE Computer Society Press USA · Zbl 0944.68133 |
| [5] | Das, Sukanta; Kundu, Anirban; Sikdar, Biplab K.; Chaudhuri, P. Pal, Design of Nonlinear CA Based TPG Without Prohibited Pattern Set In Linear Time, Journal of Electronic Testing: Theory and Applications, 21, 95-109 (January 2005) |
| [6] | Sukanta Das and Biplab K Sikdar. Classification of CA Rules Targeting Synthesis of Reversible Cellular Automata. In Proceedings of International Conference on Cellular Automata for Research and Industry, ACRI, France, pages 68-77, September 2006; Sukanta Das and Biplab K Sikdar. Classification of CA Rules Targeting Synthesis of Reversible Cellular Automata. In Proceedings of International Conference on Cellular Automata for Research and Industry, ACRI, France, pages 68-77, September 2006 · Zbl 1155.68458 |
| [7] | Sukanta Das, Biplab K Sikdar, and P Pal Chaudhuri. Characterization of Reachable/Nonreachable Cellular Automata States. In Proceedings of Sixth International Conference on Cellular Automata for Research and Industry, ACRI, The Netherlands, pages 813-822, October 2004; Sukanta Das, Biplab K Sikdar, and P Pal Chaudhuri. Characterization of Reachable/Nonreachable Cellular Automata States. In Proceedings of Sixth International Conference on Cellular Automata for Research and Industry, ACRI, The Netherlands, pages 813-822, October 2004 · Zbl 1116.68509 |
| [8] | Hortensius, P. D.; McLeod, R. D.; Pries, W.; Card, H. C., Cellular Automata Based Pseudorandom Number Generators for Built-In Self-Test, IEEE Trans. on CAD, 8, 8, 842-859 (August 1989) |
| [9] | Kurka, P., Zero-dimensional dynamical systems formal languages and universality, Theory of Computing Systems, 32, 423-433 (1999) · Zbl 0934.68053 |
| [10] | Margara, L.; Mauri, G.; Cattaneo, G.; Formenti, E., On the dynamical behavior of chaotic cellular automata, Theoretical Computer Science, 217, 31-51 (1999) · Zbl 0933.68096 |
| [11] | Moore, Edward F., Machine models of self reproduction, (Burks, Arthur W., Essays on Cellular Automata (1970), University of Illinois Press: University of Illinois Press Urbana) · Zbl 0233.94026 |
| [12] | Myhill, J., The converse of moore’s garden of eden theorem, Proceedings of American Mathematical Society, 14, 685-686 (1963) · Zbl 0126.32501 |
| [13] | Toffoli, T.; Margolus, N., Invertible cellular automata: A review, Physica D, 45, 229 (1990) · Zbl 0729.68066 |
| [14] | Toffoli, T.; Margolus, N. H., Invertible cellular automata : A review, Physica D, 45, 229-253 (1990) · Zbl 0729.68066 |
| [15] | von Neumann, John, The theory of self-reproducing Automata, (Burks, A. W. (1966), Univ. of Illinois Press: Univ. of Illinois Press Urbana and London) · Zbl 0247.94029 |
| [16] | Wolfram, S., Statistical mechanics of cellular automata. Rev. Mod. Phys., 55, 3, 601-644 (July 1983) · Zbl 1174.82319 |
| [17] | Wolfram, S., Cellular Automata Complexity — Collected Papers. (1994), Addison Wesley · Zbl 0823.68003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
