title: Parity problem with a cellular automaton solution.
abstract: 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.
authors.affiliation: Department of Physics, University of Hong Kong, Pokfulam Road, Hong Kong.
authors.forename: K M
authors.initials: KM
authors.lastname: Lee
authors.forename: H
authors.initials: H
authors.lastname: Xu
authors.forename: H F
authors.initials: HF
authors.lastname: Chau