A max-plus model of asynchronous cellular automata

This paper presents a new framework for asynchrony. This has its origins in our attempts to better harness the internal decision-making process of cellular automata (CA). Thus, we show that a max-plus algebraic model of asynchrony arises naturally from the CA requirement that a cell receive the stat...

Full description

Bibliographic Details
Main Authors: Patel, E, Broomhead, D
Format: Journal article
Language:English
Published: Complex Systems Publications Inc 2014
_version_ 1797058984433156096
author Patel, E
Broomhead, D
author_facet Patel, E
Broomhead, D
author_sort Patel, E
collection OXFORD
description This paper presents a new framework for asynchrony. This has its origins in our attempts to better harness the internal decision-making process of cellular automata (CA). Thus, we show that a max-plus algebraic model of asynchrony arises naturally from the CA requirement that a cell receive the state of each neighbor before updating. The significant result is the existence of a bijective mapping between the asynchronous system and the synchronous system classically used to update CA. Consequently, although the CA outputs look qualitatively different, when surveyed on "contours" of real time, the asynchronous CA replicates the synchronous CA. Moreover, this type of asynchrony is simple—it is characterized by the underlying network structure of the cells, and long-term behavior is deterministic and periodic due to the linearity of max-plus algebra. The findings lead us to proffer max-plus algebra as: (i) a more accurate and efficient underlying timing mechanism for models of patterns seen in nature; and (ii) a foundation for promising extensions and applications.
first_indexed 2024-03-06T19:57:48Z
format Journal article
id oxford-uuid:263e4a1f-e790-4e1d-aee9-2702a50c46ee
institution University of Oxford
language English
last_indexed 2024-03-06T19:57:48Z
publishDate 2014
publisher Complex Systems Publications Inc
record_format dspace
spelling oxford-uuid:263e4a1f-e790-4e1d-aee9-2702a50c46ee2022-03-26T11:59:48ZA max-plus model of asynchronous cellular automataJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:263e4a1f-e790-4e1d-aee9-2702a50c46eeEnglishOxford University Research Archive - ValetComplex Systems Publications Inc2014Patel, EBroomhead, DThis paper presents a new framework for asynchrony. This has its origins in our attempts to better harness the internal decision-making process of cellular automata (CA). Thus, we show that a max-plus algebraic model of asynchrony arises naturally from the CA requirement that a cell receive the state of each neighbor before updating. The significant result is the existence of a bijective mapping between the asynchronous system and the synchronous system classically used to update CA. Consequently, although the CA outputs look qualitatively different, when surveyed on "contours" of real time, the asynchronous CA replicates the synchronous CA. Moreover, this type of asynchrony is simple—it is characterized by the underlying network structure of the cells, and long-term behavior is deterministic and periodic due to the linearity of max-plus algebra. The findings lead us to proffer max-plus algebra as: (i) a more accurate and efficient underlying timing mechanism for models of patterns seen in nature; and (ii) a foundation for promising extensions and applications.
spellingShingle Patel, E
Broomhead, D
A max-plus model of asynchronous cellular automata
title A max-plus model of asynchronous cellular automata
title_full A max-plus model of asynchronous cellular automata
title_fullStr A max-plus model of asynchronous cellular automata
title_full_unstemmed A max-plus model of asynchronous cellular automata
title_short A max-plus model of asynchronous cellular automata
title_sort max plus model of asynchronous cellular automata
work_keys_str_mv AT patele amaxplusmodelofasynchronouscellularautomata
AT broomheadd amaxplusmodelofasynchronouscellularautomata
AT patele maxplusmodelofasynchronouscellularautomata
AT broomheadd maxplusmodelofasynchronouscellularautomata