Structural and behavioral equivalence relations in automata networks
Takashi Kei SAITO, Hidenosuke Nishio · Theoretical Computer Science · 1985
We formulate the automata network as an edge- and vertex-labeled directed graph. A vertex-label corresponds to the finite automaton which is placed at the vertex and an edge-label corresponds to the label of the input terminal of a finite automaton on the vertex. In this paper, we define, on the set of vertices, the structural equivalence relation induced by the structure of the graph and the behavioral equivalence relation induced by the behavior (i.e., state transition) of the finite automaton on each vertex and discuss the structure and behavior of the network by investigating the relationships between these relations. We have obtained some interesting results, in particular about the element-uniform system.