Non-Abelian Cellular Automata

Cristopher Moore

Working Papers from Santa Fe Institute

Abstract: We show that a wide variety of nonlinear cellular automata can be written as a semidirect product of linear ones, and that these CAs can be predicted in parallel time [cal O](log[super 2] t). This class includes any CA whose rule, when written as an algebra, is a solvable group.

We also show, with an induction on levels of commutators, that CAs based on nilpotent groups can be predicted in parallel time [cal O](log t).

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-081

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 ().