Abstract
This paper reports characterization of reachable/nonreachable states of 3-neighborhood non-homogeneous Cellular Automata (CA). An efficient scheme to identify nonreachable states in O(n) time is proposed. It also computes the number of such states in O(n) time. The reported characterization of nonreachable states provides the theoretical background to identify and synthesize a reversible CA in linear time.
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
Neumann, J.V.: The Theory of Self Reproducing Automata. In: Burks, A.W. (ed.). University of Illinois Press, Urbana (1966)
Wolfram, S.: Theory and application of cellular automata. World Scientific, Singapore (1986)
Pal Chaudhuri, P., Roy Choudhury, D., Nandi, S., Chattopadhyay, S.: Additive Cellular Automata Theory and Applications. IEEE Computer Society Press, USA
Das, S., Kundu, A., Sen, S., Sikdar, B.K., Chaudhuri, P.P.: Non-Linear Cellular Automata Based PRPG Design (Without Prohibited Pattern Set) In Linear Time Complexity. In: Asian Test Conference (2003)
Wolfram, S., Martin, O., Odlyzko, A.M.: Algebraic Properties of Cellular Automata. Communications in Mathematical Physics 93, 219–258 (1984)
Wuensche, A.: Attractor Basins of Discrete Networks. Cognitive Science Research Paper, The University of Sussex (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, S., Sikdar, B.K., Chaudhuri, P.P. (2004). Characterization of Reachable/Nonreachable Cellular Automata States. In: Sloot, P.M.A., Chopard, B., Hoekstra, A.G. (eds) Cellular Automata. ACRI 2004. Lecture Notes in Computer Science, vol 3305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30479-1_84
Download citation
DOI: https://doi.org/10.1007/978-3-540-30479-1_84
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23596-5
Online ISBN: 978-3-540-30479-1
eBook Packages: Springer Book Archive