On the limit set of some universal cellular automata

Eric Goles; Alejandro Maass; Servet Martinez

doi:10.1016/0304-3975(93)90350-3

On the limit set of some universal cellular automata

Eric Goles
, Alejandro Maass
, Servet Martinez

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

9 Citas (Scopus)

Resumen

In this paper we construct a simulation of a Turing machine by cellular automata based on the equivalence between programmable machines and Turing machines. For this class of cellular automata we prove that the associated limit language is regular. We also introduce algebraic characteristics which reduce the study of the complexity of the limit language to the analysis of a class of one-symbol languages.

Idioma original	Inglés
Páginas (desde-hasta)	53-78
Número de páginas	26
Publicación	Theoretical Computer Science
Volumen	110
N.º	1
DOI	https://doi.org/10.1016/0304-3975(93)90350-3
Estado	Publicada - 15 mar. 1993
Publicado de forma externa	Sí

Acceder al documento

10.1016/0304-3975(93)90350-3

Citar esto

@article{c5e7bdcafd234fe387c000c3199a4c66,

title = "On the limit set of some universal cellular automata",

abstract = "In this paper we construct a simulation of a Turing machine by cellular automata based on the equivalence between programmable machines and Turing machines. For this class of cellular automata we prove that the associated limit language is regular. We also introduce algebraic characteristics which reduce the study of the complexity of the limit language to the analysis of a class of one-symbol languages.",

author = "Eric Goles and Alejandro Maass and Servet Martinez",

note = "Funding Information: Correspondence to: E. Gales, Universidad de Chile, Facultad de Ciencias Fisicas y Matematicas, tamento de Ingenieria Matematica, Casilla 170-3 correo 3, Santiago, Chile. *This work has been done under grants FONDECYT 1211-91, 0040-90, 1208-91.",

year = "1993",

month = mar,

day = "15",

doi = "10.1016/0304-3975(93)90350-3",

language = "English",

volume = "110",

pages = "53--78",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - On the limit set of some universal cellular automata

AU - Goles, Eric

AU - Maass, Alejandro

AU - Martinez, Servet

N1 - Funding Information: Correspondence to: E. Gales, Universidad de Chile, Facultad de Ciencias Fisicas y Matematicas, tamento de Ingenieria Matematica, Casilla 170-3 correo 3, Santiago, Chile. *This work has been done under grants FONDECYT 1211-91, 0040-90, 1208-91.

PY - 1993/3/15

Y1 - 1993/3/15

N2 - In this paper we construct a simulation of a Turing machine by cellular automata based on the equivalence between programmable machines and Turing machines. For this class of cellular automata we prove that the associated limit language is regular. We also introduce algebraic characteristics which reduce the study of the complexity of the limit language to the analysis of a class of one-symbol languages.

AB - In this paper we construct a simulation of a Turing machine by cellular automata based on the equivalence between programmable machines and Turing machines. For this class of cellular automata we prove that the associated limit language is regular. We also introduce algebraic characteristics which reduce the study of the complexity of the limit language to the analysis of a class of one-symbol languages.

UR - https://www.scopus.com/pages/publications/0027559050

U2 - 10.1016/0304-3975(93)90350-3

DO - 10.1016/0304-3975(93)90350-3

M3 - Article

AN - SCOPUS:0027559050

SN - 0304-3975

VL - 110

SP - 53

EP - 78

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

On the limit set of some universal cellular automata

Resumen

Acceder al documento

Huella

Citar esto