Detecting synchronization in spatially extended discrete systems by complexity measurements
(http://arxiv.org/abs/nlin/0411063)
I feel ambigous about this paper. On the one hand, it's about cellular automata, and I like cellular automata a lot. It has a short and very specific definition of the things he's studying:
Two L-cell cellular automata with the same evolution rule are started from different random initial conditions for each automaton. Then at each time step, the dynamics of the coupled CA is goverened by the successive application of two evolution operators; the independent evolution of each CA according to its corresponding rule and the application of a stochastic operator that compares the states sigma^{1}_{i} and sigma^{2}_{i} of all the cells i, ..., L in each automaton. If sigma^{1}_{i} = sigma^{2}_i, both states are kept invariant. If sigma^{1}_{i} != sigma^{2}_{i}, they are left unchanged with probability 1-p, but both states are updated to either to sigma^{1}_{i} or to sigma ^{2}_{i} with equal probability.
There are pretty pictures in the back, both of coupled cellular automata, and of the complexity peaking at medium values of p.
On the other hand, the author clearly likes this "LMC" complexity measure (which seems pretty ad-hoc to me) a lot (he is the L), and the task of detecting when two CAs synchronize is pretty easy - when the difference automaton goes solid, they're synchronized. He doesn't give any alternative measures of complexity.
About "LMC complexity":
This is a function from a histogram to a number. On the one hand, you can compute the Shannon entropy of a histogram - as the histogram goes from spiky to flat, the entropy will go from low to high. On the other hand, you can consider the histogram to be a point in n-dimensional space, and directly measure the euclidean distance to a flat histogram - as the histogram goes from spiky to flat, this distance will go from high to low.
If you multiply these two measures together, you get LMC complexity, which goes from low to high to low. It is high for "medium spiky" histograms.
I recommend browsing this paper, because it's only 4 pages, 2 of which are figures.
I feel ambigous about this paper. On the one hand, it's about cellular automata, and I like cellular automata a lot. It has a short and very specific definition of the things he's studying:
Two L-cell cellular automata with the same evolution rule are started from different random initial conditions for each automaton. Then at each time step, the dynamics of the coupled CA is goverened by the successive application of two evolution operators; the independent evolution of each CA according to its corresponding rule and the application of a stochastic operator that compares the states sigma^{1}_{i} and sigma^{2}_{i} of all the cells i, ..., L in each automaton. If sigma^{1}_{i} = sigma^{2}_i, both states are kept invariant. If sigma^{1}_{i} != sigma^{2}_{i}, they are left unchanged with probability 1-p, but both states are updated to either to sigma^{1}_{i} or to sigma ^{2}_{i} with equal probability.
There are pretty pictures in the back, both of coupled cellular automata, and of the complexity peaking at medium values of p.
On the other hand, the author clearly likes this "LMC" complexity measure (which seems pretty ad-hoc to me) a lot (he is the L), and the task of detecting when two CAs synchronize is pretty easy - when the difference automaton goes solid, they're synchronized. He doesn't give any alternative measures of complexity.
About "LMC complexity":
This is a function from a histogram to a number. On the one hand, you can compute the Shannon entropy of a histogram - as the histogram goes from spiky to flat, the entropy will go from low to high. On the other hand, you can consider the histogram to be a point in n-dimensional space, and directly measure the euclidean distance to a flat histogram - as the histogram goes from spiky to flat, this distance will go from high to low.
If you multiply these two measures together, you get LMC complexity, which goes from low to high to low. It is high for "medium spiky" histograms.
I recommend browsing this paper, because it's only 4 pages, 2 of which are figures.
posted by Johnicholas at 11:28 AM
0 Comments:
Post a Comment
<< Home