Abstract
We present stochastic cellular automata that classify the parity of initial conditions. The model is an interacting particles system where cells are updated by pairs, randomly chosen at each time step. A first rule is proposed, with a symmetry between 0’s and 1’s. We show that it classifies the parity of the initial configurations thanks to a non-biased random walk of the frontiers between 0’s and 1’s. We present an analysis of the classification time, as well as numerical simulations, to establish that the classification time scales quadratically with the number of cells. In a second time, breaking the state symmetry, we propose an improvement of this rule with the simultaneous use of two classifying systems.
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
Similar content being viewed by others
Notes
- 1.
The solution that was initially published is possibly altered by a mistake, which nevertheless does not compromise the whole construction [private communications].
References
Sipper, M.: Computing with cellular automata: three cases for nonuniformity. Phys. Rev. E 57, 3589–3592 (1998). https://doi.org/10.1103/PhysRevE.57.3589
Betel, H., de Oliveira, P.P.B., Flocchini, P.: Solving the parity problem in one-dimensional cellular automata. Nat. Comput. 12(3), 323–337 (2013). https://doi.org/10.1007/s11047-013-9374-9
Ruivo, E.L.P., de Oliveira, P.P.B.: A perfect solution to the parity problem with elementary cellular automaton 150 under asynchronous update. Inform. Sci. 493, 138–151 (2019). https://doi.org/10.1016/j.ins.2019.04.045
Ruivo, E.L.P., Balbi, P.P., Perrot, K.: An asynchronous solution to the synchronisation problem for binary one-dimensional cellular automata. Physica D 413, 132554 (2020). https://doi.org/10.1016/j.physd.2020.132554
Balbi, P.P., Ruivo, E., Faria, F.: Synchronous solution of the parity problem on cyclic configurations, with elementary cellular automaton rule 150, over a family of directed, non-circulant, regular graphs. Inform. Sci. 615, 578–603 (2022). https://doi.org/10.1016/j.ins.2022.10.045
Fatès, N.: Asynchronous cellular automata. In: Encyclopedia of Complexity and Systems Science, pp. 1–21. Springer, Berlin (2018). https://doi.org/10.1007/978-3-642-27737-5_671-2
Peper, F., Lee, J., Isokawa, T.: Brownian cellular automata. J. Cell. Autom. 5(3), 185–206 (2010)
Regnault, D., Rémila, É.: Lost in self-stabilization: a local process that aligns connected cells. Theoret. Comput. Sci. 736, 41–61 (2018). https://doi.org/10.1016/j.tcs.2018.02.015
Fukś, H.: Nondeterministic density classification with diffusive probabilistic cellular automata. Phys. Rev. E 66(6), 066106 (2002). https://doi.org/10.1103/PhysRevE.66.066106
Schüle, M., Ott, T., Stoop, R.: Computing with probabilistic cellular automata. In: Alippi, C., Polycarpou, M., Panayiotou, C., Ellinas, G. (eds.) ICANN 2009. LNCS, vol. 5769, pp. 525–533. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04277-5_53
Fatès, N.: Stochastic cellular automata solutions to the density classification problem - when randomness helps computing. Theory Comput. Syst. 53(2), 223–242 (2013). https://doi.org/10.1007/s00224-012-9386-3
Fatès, N.: Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models. Nat. Comput. 18(3), 429–444 (2019). https://doi.org/10.1007/s11047-018-9683-0
Acknowledgments
The author wishes to express his sincere gratitude to Barbara Wolnik (univ. of Gdansk, Poland) and Irène Marcovici (univ. of Rouen, France) for their precious advice and remarks. The comments of the anonymous reviewers were a great help to improve the manuscript.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The author have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2024 IFIP International Federation for Information Processing
About this paper
Cite this paper
Fatès, N. (2024). Asynchronous Cellular Systems that Solve the Parity Problem. In: Gadouleau, M., Castillo-Ramirez, A. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2024. Lecture Notes in Computer Science, vol 14782. Springer, Cham. https://doi.org/10.1007/978-3-031-65887-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-65887-7_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-65886-0
Online ISBN: 978-3-031-65887-7
eBook Packages: Computer ScienceComputer Science (R0)