Abstract
To determine the computational capacity of cellular automata they are often investigated towards their ability to accept formal languages within certain time constraints. In this paper, we take up an opposite position and look at cellular automata towards their ability to generate formal languages, here called patterns, within certain time constraints. As an example we describe a construction of a cellular automaton that generates prefixes of the well-known Thue-Morse sequence within real time. Furthermore, we study the real-time generation of unary patterns in depth and obtain a characterization by time-constructible functions and their corresponding unary formal languages.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Choffrut, C., Čulik II, K.: On real-time cellular automata and trellis automata. Acta Inform. 21, 393–407 (1984)
Dyer, C.R.: One-way bounded cellular automata. Inform. Control 44(3), 261–281 (1980)
Fischer, P.C.: Generation of primes by a one-dimensional real-time iterative array. J. ACM 12, 388–394 (1965)
Grandjean, A., Richard, G., Terrier, V.: Linear functional classes over cellular automata. In: Formenti, E. (ed.) International workshop on Cellular Automata and Discrete Complex Systems and Journées Automates Cellulaires (AUTOMATA & JAC 2012). EPTCS, vol. 90, pp. 177–193 (2012)
Kari, J.: Universal pattern generation by cellular automata. Theor. Comput. Sci. 429, 180–184 (2012)
Kutrib, M.: Cellular automata - a computational point of view. In: Bel-Enguix, G., Jiménez-López, M.D., Martín-Vide, C. (eds.) New Developments in Formal Languages and Applications. SCI, pp. 183–227. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78291-9_6
Kutrib, M.: Cellular automata and language theory. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and Systems Science, pp. 800–823. Springer, Heidelberg (2009). https://doi.org/10.1007/978-0-387-30440-3_54
Kutrib, M., Malcher, A.: One-dimensional cellular automaton transducers. Fundam. Inform. 126(2–3), 201–224 (2013)
Mazoyer, J., Terrier, V.: Signals in one-dimensional cellular automata. Theor. Comput. Sci. 217, 53–80 (1999)
Waksman, A.: An optimum solution to the firing squad synchronization problem. Inform. Control 9, 66–78 (1966)
Wolfram, S.: Random sequence generation by cellular automata. Adv. Appl. Math. 7, 123–169 (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Kutrib, M., Malcher, A. (2021). One-Dimensional Pattern Generation by Cellular Automata. In: Gwizdałła, T.M., Manzoni, L., Sirakoulis, G.C., Bandini, S., Podlaski, K. (eds) Cellular Automata. ACRI 2020. Lecture Notes in Computer Science(), vol 12599. Springer, Cham. https://doi.org/10.1007/978-3-030-69480-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-69480-7_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-69479-1
Online ISBN: 978-3-030-69480-7
eBook Packages: Computer ScienceComputer Science (R0)