Complexity of Maxmin-ω Cellular Automata

Author: 

Patel, E

Publication Date: 

1 January 2018

Journal: 

Springer Proceedings in Complexity

Last Updated: 

2020-05-22T09:28:33.02+01:00

DOI: 

10.1007/978-3-319-96661-8_10

page: 

98-107

abstract: 

© 2018, Springer Nature Switzerland AG. We present an analysis of an additive cellular automaton (CA) under asynchronous dynamics. The asynchronous scheme employed is maxmin-ω, a deterministic system, introduced in previous work with a binary alphabet. Extending this work, we study the impact of a varying alphabet size, i.e., more than the binary states often employed. Far from being a simple positive correlation between complexity and alphabet size, we show that there is an optimal region of ω and alphabet size where complexity of CA is maximal. Thus, despite employing a fixed additive CA rule, the complexity of this CA can be controlled by ω and alphabet size. The flavour of maxmin- ω is, therefore, best captured by a CA with a large number of states.

Symplectic id: 

911264

Submitted to ORA: 

Not Submitted

Publication Type: 

Chapter