H F Chau | Search PubMed

PubMed2001

Parity problem with a cellular automaton solution.

The parity of a bit string of length N is a global quantity that can be efficiently computed using a global counter in O(N) time. But is it possible to find the parity using cellular automata with a set of local rule tables without using any global counter? Here, we report a way to solve this problem using a number of r=1 binary, uniform, parallel, and deterministic cellular automata applied in succession for a total of O(N2) time.

Journal Article↗

PubMed1999

Phase diagram of the Biham-Middleton-Levine traffic model in three dimensions.

We study numerically the behavior of the Biham-Middleton-Levine traffic model in three dimensions. Our extensive numerical simulations show that the phase diagram for this model in three dimensions is markedly different from that in one and two dimensions. In addition to the full speed moving as well as the completely jamming phases, whose respective average asymptotic car speeds (v) equal one and zero, we observe an extensive region of car densities rho with a low but nonzero average asymptotic car speed. The transition from this extensive low average asymptotic car speed region to the completely jamming region is at least second order. We argue that this low speed region is a result of the formation of a spatially limited-extended percolating cluster. Thus, this low speed phase is present in the (n>3)-dimensional Biham-Middleton-Levine model as well.

Journal Article↗