One-Dimensional Pattern Generation by Cellular Automata | SpringerLink
Skip to main content

One-Dimensional Pattern Generation by Cellular Automata

  • Conference paper
  • First Online:
Cellular Automata (ACRI 2020)

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Choffrut, C., Čulik II, K.: On real-time cellular automata and trellis automata. Acta Inform. 21, 393–407 (1984)

    Article  MathSciNet  Google Scholar 

  2. Dyer, C.R.: One-way bounded cellular automata. Inform. Control 44(3), 261–281 (1980)

    Article  MathSciNet  Google Scholar 

  3. Fischer, P.C.: Generation of primes by a one-dimensional real-time iterative array. J. ACM 12, 388–394 (1965)

    Article  MathSciNet  Google Scholar 

  4. 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)

    Google Scholar 

  5. Kari, J.: Universal pattern generation by cellular automata. Theor. Comput. Sci. 429, 180–184 (2012)

    Article  MathSciNet  Google Scholar 

  6. 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

    Chapter  Google Scholar 

  7. 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

    Chapter  Google Scholar 

  8. Kutrib, M., Malcher, A.: One-dimensional cellular automaton transducers. Fundam. Inform. 126(2–3), 201–224 (2013)

    Article  MathSciNet  Google Scholar 

  9. Mazoyer, J., Terrier, V.: Signals in one-dimensional cellular automata. Theor. Comput. Sci. 217, 53–80 (1999)

    Article  MathSciNet  Google Scholar 

  10. Waksman, A.: An optimum solution to the firing squad synchronization problem. Inform. Control 9, 66–78 (1966)

    Article  MathSciNet  Google Scholar 

  11. Wolfram, S.: Random sequence generation by cellular automata. Adv. Appl. Math. 7, 123–169 (1986)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Martin Kutrib .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics