We introduce a framework that connects two discrete models of natural computing, cellular automata (CA) and reaction systems (RS). We define pattern graphs of a CA as one-out digraphs where vertices correspond to totally periodic configurations and edges reflect CA evolution. Using pattern graphs based on periodic configurations we show that every one-dimensional binary CA can be transformed into an RS via its zero-context graph and provide counterexamples for the converse. Modified techniques, such as increasing the number of states and subgraphs of pattern graphs, are used to transform arbitrary RS into CA.

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

Pattern Graphs of Cellular Automata and Reaction Systems

  • Kyle Ambrose,
  • Daniela Genova,
  • Troy Kidd

摘要

We introduce a framework that connects two discrete models of natural computing, cellular automata (CA) and reaction systems (RS). We define pattern graphs of a CA as one-out digraphs where vertices correspond to totally periodic configurations and edges reflect CA evolution. Using pattern graphs based on periodic configurations we show that every one-dimensional binary CA can be transformed into an RS via its zero-context graph and provide counterexamples for the converse. Modified techniques, such as increasing the number of states and subgraphs of pattern graphs, are used to transform arbitrary RS into CA.