# One Dimensional $n$ary Density Classification Using Two Cellular Automaton Rules

Source: [One Dimensional $n$ary Density Classification Using Two Cellular Automaton Rules](<https://www.sota2.com/research/paper/68fa31a31e209131ce8806b6>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-24T18:58:14.801Z

Authors: H. F. Chau, L. W. Siu, K. K. Yan

Published: 1998-10-22T06:28:59.000Z

## Abstract

Suppose each site on a one-dimensional chain with periodic boundary condition may take on any one of the states $0,1,..., n-1$, can you find out the most frequently occurring state using cellular automaton? Here, we prove that while the above density classification task cannot be resolved by a single cellular automaton, this task can be performed efficiently by applying two cellular automaton rules in succession.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/adap-org/9810006>)

[PDF](<https://arxiv.org/pdf/adap-org/9810006.pdf>)
