On the limit set of some universal cellular automata

DOI10.1016/0304-3975(93)90350-3zbMath0774.68085OpenAlexW2032010938MaRDI QIDQ1210540

Alejandro Maass, Servet Martínez, Eric Goles Chacc

Publication date: 30 August 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90350-3

zbMATH Keywords

computational complexityTuring machinescellular automatamorphismlimit language complexityprogrammable machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Cellular automata (computational aspects) (68Q80)

Related Items

The relationships of three elementary cellular automata, On the sofic limit sets of cellular automata, Measure evolution of cellular automata and of finitely anticipative transformations, Bulking II: Classifications of cellular automata, Topological and measure-theoretic properties of one-dimensional cellular automata, Eric Goles, On topological dynamics of Turing machines, The mirage of universality in cellular automata

Cites Work

• Computation theory of cellular automata
• A six-state minimal time solution to the Firing squad synchronization problem
• Subshifts of finite type and sofic systems
• On the Limit Sets of Cellular Automata
• Finite state languages
• On certain formal properties of grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item