DocumentCode :
2346388
Title :
Some results on invertible cellular automata
Author :
Clementi, A. ; Mentrasti, P. ; Pierini, P.
Author_Institution :
Dept. of Comput. Sci., La Sapienza Univ., Rome, Italy
fYear :
1994
fDate :
17-20 Nov 1994
Firstpage :
143
Lastpage :
150
Abstract :
Addresses certain questions concerning invertible cellular automata, and presents new results in this area. Specifically, we explicitly construct a cellular automaton in a class (a residual class) previously known not to be empty only via a nonconstructive existence proof. This class contains cellular automata that are invertible on every finite support but not on an infinite lattice. Moreover, we show a class that contains invertible cellular automata having bounded neighborhood, but whose inverses constitute a class of cellular automata for which there isn´t any recursive function bounding all the neighborhood
Keywords :
cellular automata; bounded neighborhood; finite support; infinite lattice; invertible cellular automata; nonconstructive existence proof; nonempty class; recursive function; residual class; Automata; Computational modeling; Concurrent computing; Grid computing; Lattices; Mathematics; Physics computing; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Physics and Computation, 1994. PhysComp '94, Proceedings., Workshop on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-6715-X
Type :
conf
DOI :
10.1109/PHYCMP.1994.363688
Filename :
363688
Link To Document :
بازگشت