LIPIcs.ICALP.2016.115.pdf
- Filesize: 3.02 MB
- 12 pages
Document
A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods
Authors
-
Part of:
Volume:
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-23
Cite As Get BibTex
Anaël Grandjean and Victor Poupet. A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 115:1-115:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.115
Abstract
Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all twodimensional languages recognized by cellular automata working on complete neighborhoods.
Subject Classification
Keywords
- 2D Cellular automata
- linear acceleration
- language recognition
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
J. Albert and K. Čulik II. A simple universal cellular automaton and its one-way and totalistic version. Complex Systems, 1:1-16, 1987.
-
W.T. Beyer. Recognition of topological invariants by iterative arrays. Massachusetts Institute of Technology, Project MAC, 1969.
-
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.
- Martin Delacourt and Victor Poupet. Real time language recognition on 2d cellular automata: Dealing with non-convex neighborhoods. In Ludek Kucera and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, volume 4708 of Lecture Notes in Computer Science, pages 298-309. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74456-6_28.
-
P. C. Fischer. Generation of primes by one-dimensional real-time iterative array. Journal of the Assoc. Comput. Mach., 12:388-394, 1965.
-
F.C. Hennie. Iterative Arrays of Logical Circuits. MIT Press Classics. MIT Press, 1961.
- Jacques Mazoyer and Nicolas Reimen. A linear speed-up theorem for cellular automata. Theor. Comput. Sci., 101(1):59-98, 1992. URL: http://dx.doi.org/10.1016/0304-3975(92)90150-E.
-
Zsuzsanna Róka. Simulations between cellular automata on Cayley graphs. Theoretical Computer Science, 225(1-2):81-111, 1999.
- Alvy R. Smith III. Simple computation-universal cellular spaces. J. ACM, 18(3):339-353, 1971. URL: http://dx.doi.org/10.1145/321650.321652.
- Alvy R. Smith III. Two-dimensional formal languages and pattern recognition by cellular automata. In Proceedings of the 12th Annual Symposium on Switching and Automata Theory (Swat 1971), SWAT'71, pages 144-152, Washington, DC, USA, 1971. IEEE Computer Society. URL: http://dx.doi.org/10.1109/SWAT.1971.29.
-
Alvy R. Smith III. Real-time language recognition by one-dimensional cellular automata. Journal of the Assoc. Comput. Mach., 6:233-253, 1972.
- Véronique Terrier. Two-dimensional cellular automata recognizer. Theor. Comput. Sci., 218(2):325-346, 1999. URL: http://dx.doi.org/10.1016/S0304-3975(98)00329-6.
- Véronique Terrier. Two-dimensional cellular automata and their neighborhoods. Theor. Comput. Sci., 312(2-3):203-222, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2003.08.011.
-
John von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Urbana, IL, USA, 1966.