Simply modified GKL density classifiers that reach consensus faster

DOI10.1016/J.PHYSLETA.2019.04.033zbMATH Open1474.68200arXiv1904.07411OpenAlexW2938510648MaRDI QIDQ820909FDOQ820909

J. R. G. Mendonça

Publication date: 29 September 2021

Published in: Physics Letters. A (Search for Journal in Brave)

Abstract: The two-state Gacs-Kurdyumov-Levin (GKL) cellular automaton has been a staple model in the study of complex systems due to its ability to classify binary arrays of symbols according to their initial density. We show that a class of modified GKL models over extended neighborhoods, but still involving only three cells at a time, achieves comparable density classification performance but in some cases reach consensus more than twice as fast. Our results suggest the time to consensus (relative to the length of the CA) as a complementary measure of density classification performance.

Full work available at URL: https://arxiv.org/abs/1904.07411

zbMATH Keywords

emergencecellular automatadensity classification problemspatially distributed computing

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• Title not available (Why is that?)
• The evolution of emergent computation.
• The Gacs-Kurdyumov-Levin automaton revisited
• Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
• Density classification on infinite lattices and trees
• Around probabilistic cellular automata
• Stable multi-level monotonic eroders
• Ergodicity of some classes of cellular automata subject to noise
• On density determination with cellular automata: results, constructions and directions
• Overview: PCA Models and Issues

This page was built for publication: Simply modified GKL density classifiers that reach consensus faster

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