On the Representation of Gliders in Rule 54 by De Bruijn and Cycle Diagrams | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the Representation of Gliders in Rule 54 by De Bruijn and Cycle Diagrams

  • Conference paper
Cellular Automata (ACRI 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5191))

Included in the following conference series:

  • 1683 Accesses

Abstract

Rule 54, in Wolfram’s notation, is one of elementary yet complexly behaving one-dimensional cellular automata. The automaton supports gliders, glider guns and other non-trivial long transients. We show how to characterize gliders in Rule 54 by diagram representations as de Bruijn and cycle diagrams; offering a way to present each glider in Rule 54 with particular characteristics. This allows a compact encoding of initial conditions which can be used in implementing non-trivial collision-based computing in one-dimensional cellular automata.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Adamatzky, A. (ed.): Collision-Based Computing. Springer, Heidelberg (2003)

    Google Scholar 

  2. Boccara, N., Nasser, J., Roger, M.: Particle like structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules. Physical Review A 44(2), 866–875 (1991)

    Article  Google Scholar 

  3. Golomb, S.W.: Shift Register Sequences. Holden-Day, San Francisco (1967)

    MATH  Google Scholar 

  4. Hanson, J.E., Crutchfield, J.P.: Computacional Mechanics of Cellular Automata: An Example. Physics D 103(1-4), 169–189 (1997)

    Article  MathSciNet  Google Scholar 

  5. Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Phenomenology of glider collisions in cellular automaton Rule 54 and associated logical gates. Chaos, Solitons and Fractals 28, 100–111 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  6. Martínez, G.J., McIntosh, H.V., Seck Tuoh Mora, J.C., Chapa Vergara, S.V.: Rule 110 objects and other collision-based constructions. J. Cellular Automata 2(3), 219–242 (2007)

    MATH  Google Scholar 

  7. Martínez, G.J., McIntosh, H.V., Seck Touh Mora, J.C., Chapa Vergara, S.V.: Determining a regular language by glider-based structures called phases f i _1 in Rule 110. J. Cellular Automata (in press)

    Google Scholar 

  8. McIntosh, H.V.: Linear cellular automata via de Bruijn diagrams (1991), http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html

  9. McIntosh, H.V.: Commentaries on: The Global Dynamics of Cellular Automata (by Wuensche, A., Lesser, M.:) (1993), http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html

  10. McIntosh, H.V.: Rule 110 as it relates to the presence of gliders (1999), http://delta.cs.cinvestav.mx/~mcintosh/oldweb/pautomata.html

  11. McIntosh, H.V.: One Dimensional Cellular Automata (by publish)

    Google Scholar 

  12. Voorhees, B.H.: Computational analysis of one-dimensional cellular automata. World Scientific Series on Nonlinear Science, Series A, vol. 15 (1996)

    Google Scholar 

  13. Voorhees, B.H.: Remarks on Applications of De Bruijn Diagrams and Their Fragments. Journal of Cellular Automata (in press)

    Google Scholar 

  14. Wuensche, A., Lesser, M.: The Global Dynamics of Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley Publishing Company, Reading (1992)

    MATH  Google Scholar 

  15. Wolfram, S.: Theory and Aplications of Cellular Automata. World Scientific Press, Singapore (1986)

    Google Scholar 

  16. Wolfram, S.: A New Kind of Science. Wolfram Media, Inc., Champaign (2002)

    MATH  Google Scholar 

  17. Wuensche, A.: Classifying Cellular Automata Automatically. Complexity 4(3), 47–66 (1999)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computing, Engineering and Mathematical Sciences, University of the West of England, Bristol, United Kingdom

    Genaro J. Martínez & Andrew Adamatzky

  2. Departamento de Aplicación de Microcomputadoras, Instituto de Ciencias, Universidad Autónoma de Puebla, Puebla, México

    Harold V. McIntosh

Authors
  1. Genaro J. Martínez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrew Adamatzky
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Harold V. McIntosh
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Hiroshi Umeo Shin Morishita Katsuhiro Nishinari Toshihiko Komatsuzaki Stefania Bandini

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Martínez, G.J., Adamatzky, A., McIntosh, H.V. (2008). On the Representation of Gliders in Rule 54 by De Bruijn and Cycle Diagrams. In: Umeo, H., Morishita, S., Nishinari, K., Komatsuzaki, T., Bandini, S. (eds) Cellular Automata. ACRI 2008. Lecture Notes in Computer Science, vol 5191. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79992-4_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-79992-4_11

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-79991-7

  • Online ISBN: 978-3-540-79992-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation