Quasi-Linear Cellular Automata

Cristopher Moore

Working Papers from Santa Fe Institute

Abstract: Simulating a cellular automata (CA) for t time-steps into the future requires t[super 2] serial computation steps or t parallel ones. However, certain CAs based on an Abelian group, such as addition mod 2, are termed linear because they obey a principle of superposition. This allows them to be predicted effiently, in serial time [cal O](t) [1] or [cal O](log t) in parallel.

In this paper, we generalize this by looking at CAs with a variety of algebraic structures, including quasigroups, non-Abelian groups, Steiner systems, and other structures. We show that in many cases, an efficient algorithm exists even though these CAs are not linear in the previous sense; we term them quasilinear. We find examples which can be predicted in serial time proportional to t, tlog t tlog[super 2] and t[super alpha] for alpha

Date: 1995-09
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:95-09-078

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().