Document Open Access Logo

Comparing 1D and 2D Real Time on Cellular Automata

Authors Anaël Grandjean, Victor Poupet

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2015.367.pdf
  • Filesize: 3.03 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Cellular automata
  • real time
  • language recognition

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.

Cite As Get BibTex

Anaël Grandjean and Victor Poupet. Comparing 1D and 2D Real Time on Cellular Automata. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 367-378, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.367

Author Details

Anaël Grandjean
Victor Poupet

References

  1. Stephen N. Cole. Real-time computation by n-dimensional iterative arrays of finite-state machines. IEEE Transactions on Computers, C-18(4):349-365, 1969. Google Scholar
  2. Marianne Delorme, Enrico Formenti, and Jacques Mazoyer. Open problems on cellular automata. Technical report, LIP - ENS Lyon, 2000. Google Scholar
  3. Oscar H. Ibarra and Tao Jiang. Relating the power of cellular arrays to their closure properties. Theoretical Computer Science, 57(2-3):225-238, 1988. Google Scholar
  4. Jacques Mazoyer and Nicolas Reimen. A linear speed-up theorem for cellular automata. Theor. Comput. Sci., 101(1):59-98, 1992. Google Scholar
  5. Alvy R. Smith III. Simple computation-universal cellular spaces. J. ACM, 18(3):339-353, 1971. Google Scholar
  6. Véronique Terrier. Low complexity classes of multidimensional cellular automata. Theor. Comput. Sci., 369(1-3):142-156, 2006. Google Scholar
  7. John von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Urbana, IL, USA, 1966. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact