Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Computational Aspects of Cellular Automata on Countable Sofic Shifts

  • Conference paper
Mathematical Foundations of Computer Science 2012 (MFCS 2012)

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

Abstract

We investigate the computational properties of cellular automata on countable (equivalently, zero entropy) sofic shifts with an emphasis on nilpotency, periodicity, and asymptotic behavior. As a tool for proving decidability results, we prove the Starfleet Lemma, which is of independent interest. We present computational results including the decidability of nilpotency and periodicity, the undecidability of stability of the limit set, and the existence of a \(\mathrm{\Pi}^0_1\)-complete limit set and a \(\mathrm{\Sigma}^0_3\)-complete asymptotic set.

Research supported by the Academy of Finland Grant 131558.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • 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

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Guillon, P., Richard, G.: Asymptotic behavior of dynamical systems and cellular automata. ArXiv e-prints (2010)

    Google Scholar 

  2. Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21, 571–586 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  3. Kari, J.: Rice’s theorem for the limit sets of cellular automata. Theoret. Comput. Sci. 127, 229–254 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ballier, A., Durand, B., Jeandel, E.: Structural aspects of tilings. In: Susanne Albers, P.W. (ed.) Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science, Bordeaux, France, pp. 61–72, 11 pages. IBFI Schloss Dagstuhl (2008)

    Google Scholar 

  5. Morita, K.: Universality of a reversible two-counter machine. Theoretical Computer Science (1996)

    Google Scholar 

  6. Guillon, P., Richard, G.: Asymptotic behavior of dynamical systems and cellular automata. ArXiv e-prints (April 2010)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. TUCS – Turku Centre for Computer Science, Finland

    Ville Salo

  2. University of Turku, Finland

    Ville Salo & Ilkka Törmä

Authors
  1. Ville Salo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ilkka Törmä
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Comenius University, Mlynska Dolina, 84248, Bratislava, Slovakia

    Branislav Rovan

  2. Department of Electronics and Computer Science, University of Southampton, SO17 1BJ, Southampton, UK

    Vladimiro Sassone

  3. Institute of Theoretical Computer Science, ETH Zürich, CAB H 39.2, Universitätstrasse 6, 8092, Zürich, Switzerland

    Peter Widmayer

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Salo, V., Törmä, I. (2012). Computational Aspects of Cellular Automata on Countable Sofic Shifts. In: Rovan, B., Sassone, V., Widmayer, P. (eds) Mathematical Foundations of Computer Science 2012. MFCS 2012. Lecture Notes in Computer Science, vol 7464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32589-2_67

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-32589-2_67

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-32588-5

  • Online ISBN: 978-3-642-32589-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation