Structural and behavioral equivalence relations in automata networks (Q1116701)

Let us consider a generalization of the cellular automaton notion by removing its uniformity requirements. Resulting system consisting of intercommunicating finite automata is called (nonuniform) automata network. The paper introduces some relations on the vertex set of a network, namely the structural equivlence relation (SER) and the behavioral equivalence relation (BER) in order to use the same framework to discuss the static and dynamic properties (i.e., the structure and behavior) of a network. The article first of all defines formally the automata network, then defines SER and establishes basic properties of \({\mathcal S}_{A}\), the set of all SER's of the automata network A. By a similar way it treats BER and \({\mathcal B}_ A\) and then discusses the relationships between \({\mathcal S}_ A\) and \({\mathcal B}_ A\). Finally it studies the structure of \({\mathcal S}_ A\) in the case where A is a cellular automata, i.e., an identical automaton is placed at every vertex of a network A.