Premium
Stability of vertices in random boolean cellular automata
Author(s) -
Luczak Tomasz,
Cohen Joel E.
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020307
Subject(s) - cellular automaton , mathematical proof , mathematics , automaton , combinatorics , block cellular automaton , fraction (chemistry) , discrete mathematics , computer science , algorithm , theoretical computer science , mobile automaton , automata theory , chemistry , geometry , organic chemistry
Based on computer simulations, Kauffman ( Physica D , 10, 145‐156, 1984) made several generalizations about a random Boolean cellular automaton which he invented as a model of cellular metabolism. Here we give the first rigorous proofs of two of Kauffman's generalizations: a large fraction of vertices stabilize quickly, consequently the length of cycles in the automaton's behavior is small compared to that of a random mapping with the same number of states; and reversal of the states of a large fraction of the vertices does not affect the cycle to which the automaton moves.