Abstract
Decision problems addressed by cellular automata have been historically expressed either as determining whether initial configurations would belong to a given language, or as classifying the initial configurations according to a property in them. Unlike traditional approaches in language recognition, classification problems have typically relied upon cyclic configurations and fully paralell (two-way) update of the cells, which render the action of the cellular automaton relatively less controllable and difficult to analyse. Although the notion of cyclic languages have been studied in the wider realm of formal languages, only recently a more systematic attempt has come into play in respect to cellular automata with fully parallel update. With the goal of contributing to this effort, we propose a unified definition of classification problem for one-dimensional, binary cellular automata, from which various known problems are couched in and novel ones are defined, and analyse the solvability of the new problems. Such a unified perspective aims at increasing existing knowledge about classification problems by cellular automata over cyclic configurations and parallel update.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Auer C, Wüchner P, De Meer H (2011) Target-oriented self-structuring in classifying cellular automata. J Cell Autom 6(1):25–52
Bacquey N (2014) Complexity classes on spatially periodic cellular automata. In: Mayr EW, Portier N (eds) 31st International symposium on theoretical aspects of computer science (STACS 2014), Leibniz international proceedings in informatics (LIPIcs), vol. 25, pp 112–124. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany. http://drops.dagstuhl.de/opus/volltexte/2014/4451
Betel H, de Oliveira PPB, Flocchini P (2013) Solving the parity problem in one-dimensional cellular automata. Nat Comput 12(3):323–337
Chau HF, Siu LW, Yan KK (1999) One dimensional n-ary density classification using two cellular automaton rules. Int J Mod Phys C 10(05):883–887
de Oliveira PPB (2014) On density determination with cellular automata: results, constructions and directions. J Cell Autom 9(5–6):357–385
Fatès N (2015) Remarks on the cellular automaton global synchronisation problem. Springer, Berlin, Heidelberg, pp 113–126. https://doi.org/10.1007/978-3-662-47221-7_9
Gramß T, Bornholdt S, Groß M, Mitchell M, Pellizzari T (2005) Computation in cellular automata: a selected review. Wiley-VCH Verlag GmbH & Co. KGaA, Hoboken, pp 95–140. https://doi.org/10.1002/3527602968.ch4
Kari J (2005) Theory of cellular automata: a survey. Theor Comput Sci 334(1):3–33
Kutrib M (2009) Cellular automata and language theory. In: Meyers RA (ed) Encyclopedia of complexity and systems science. Springer, Berlin, pp 800–823
Land M, Belew RK (1995) No perfect two-state cellular automata for density classification exists. Phys Rev Lett 74(25):5148–5150
Mazoyer J, Yunès JB (2012) Computations on cellular automata. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92910-9_5
Terrier V (2012) Language recognition by cellular automata. In: Rozenberg G, Bäck T, Kok JN (eds) Handbook of natural computing. Springer, Berlin, pp 123–158
Wolfram S (2002) A new kind of science, vol 5. Wolfram Media, Champaign
Acknowledgements
This work was partially supported by FONDECYT 1140090 (E.G.), FONDECYT Iniciación 11150827 (M.M-M.), Basal CMM, as well as the Brazilian funding agencies, MackPesquisa—Fundo Mackenzie de Pesquisa and FAPESP.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Montalva-Medel, M., de Oliveira, P.P.B. & Goles, E. A portfolio of classification problems by one-dimensional cellular automata, over cyclic binary configurations and parallel update. Nat Comput 17, 663–671 (2018). https://doi.org/10.1007/s11047-017-9650-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-017-9650-1