Simply modified GKL density classifiers that reach consensus faster

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

Authors: 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

Recommendations

• Modified traffic cellular automaton for the density classification task
• A very effective density classifier two-dimensional cellular automaton with memory
• Restricted density classification in one dimension
• An exact solution to the two-dimensional arbitrary-threshold density classification problem
• Solving two-dimensional density classification problem with two probabilistic cellular automata

zbMATH Keywords

emergencecellular automatadensity classification problemspatially distributed computing

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• 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
• Title not available (Why is that?)
• 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)