Quasilinear cellular automata

DOI10.1016/S0167-2789(96)00255-2zbMATH Open1194.37023arXivadap-org/9701001OpenAlexW2026161213MaRDI QIDQ992263FDOQ992263

Cristopher Moore

Publication date: 11 September 2010

Published in: Physica D (Search for Journal in Brave)

Abstract: Simulating a cellular automaton (CA) for t time-steps into the future requires t^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 efficiently, in serial time O(t) or 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 others. 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, t log t, t log^2 t, and t^a for a < 2, and parallel time log t, log t log log t and log^2 t. We also discuss what algebraic properties are required or implied by the existence of scaling relations and principles of superposition, and exhibit several novel ``vector-valued CAs.

Full work available at URL: https://arxiv.org/abs/adap-org/9701001

Recommendations

• Predicting nonlinear cellular automata quickly by decomposing them into linear ones
• Selfsimilarity, simulation and spacetime symmetries
• scientific article
• scientific article
• A universal cellular automaton in quasi-linear time and its S-m-n form

Mathematics Subject Classification ID

Dynamical aspects of cellular automata (37B15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistical mechanics of cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algebraic properties of cellular automata
• Title not available (Why is that?)
• Co-Ordinatizing Steiner Systems
• Cyclic cellular automata and related processes
• Title not available (Why is that?)
• Turbulent pattern bases for cellular automata
• Demosian Systems of Quasigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (14)

• On principles of emergent organization
• Efficient exhaustive listings of reversible one dimensional cellular automata
• On the complexity of two-dimensional signed majority cellular automata
• Circuits and expressions with nonassociative gates
• Linear cellular automata with boundary conditions
• Algebraic properties of some quadratic dynamical systems
• The Complexity of Small Universal Turing Machines: A Survey
• Insights gained after a decade of cellular automata-based cryptography
• The Pascal matroid as a home for generating sets of cellular automata configurations defined by quasigroups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Enumeration of maximal cycles generated by orthogonal cellular automata
• The complexity of small universal Turing machines: A survey
• Graph-theoretical characterization of invertible cellular automata

This page was built for publication: Quasilinear cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q992263)