<p>For a group <i>G</i> and a finite set <i>A</i>, a cellular automaton is a transformation of the configuration space <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(A^G\)</EquationSource> </InlineEquation> defined via a finite neighborhood and a local map. Although neighborhoods are not unique, every CA admits a unique <i>minimal neighborhood</i>, which consists of all the essential cells in <i>G</i> that affect the behavior of the local map. An <i>active transition</i> of a cellular automaton is a pattern that produces a change in the current state of a cell when the local map is applied. In this paper, we study the links between the minimal neighborhood and the number of active transitions, known as the <i>activity value</i>, of cellular automata. Our main results state that the activity value usually imposes several restrictions on the size of the minimal neighborhood of local maps.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Connections between the minimal neighborhood and the activity value of cellular automata

  • Alonso Castillo-Ramirez,
  • Eduardo Veliz-Quintero

摘要

For a group G and a finite set A, a cellular automaton is a transformation of the configuration space \(A^G\) defined via a finite neighborhood and a local map. Although neighborhoods are not unique, every CA admits a unique minimal neighborhood, which consists of all the essential cells in G that affect the behavior of the local map. An active transition of a cellular automaton is a pattern that produces a change in the current state of a cell when the local map is applied. In this paper, we study the links between the minimal neighborhood and the number of active transitions, known as the activity value, of cellular automata. Our main results state that the activity value usually imposes several restrictions on the size of the minimal neighborhood of local maps.