A note on isomorphic simulation of automata by networks of two-state automata (Q1173982)

Let \(A,B\) be automata. Then \(A\) is isomorphically simulated by \(B\) if the transformation semigroup \(T(A)\) can be embedded into \(T(B)\). (The transformation semigroup \(T(A)\) of an automaton \(A=(A,X,\delta)\) is the couple \((A,S(A))\), where \(S(A)=\{f_ x; x\in X\}\), \(f_ x(a)=\delta(a,x).)\) Given a family of automata \(A_ i=(A_ i,X_ i,\delta_ i)\), \(i\in I\), and a family of mappings \(\varphi_ i:A\times X\to X_ i\), \(i\in I\), where \(A=\prod(A_ i; i\in I)\). Then a general product of \(A_ i\), \(i\in I\), with the feedback functions \(\varphi_ i\) is the automaton \(A=(A,X,\delta)\) where \(\delta\) is defined by \[ \pi_ i(\delta(a,x))=\delta_ i(\pi_ i(a), \varphi_ i(a,x)) \] for every \(i\in I\) (\(\pi_ i\) is the \(i\)-th projection). Let \(D=(V,E)\) be a directed graph (it may contain loops). Then a general product \(A\) of \(A_ v\), \(v\in V\), with the feedback functions \(\varphi_ v\), \(v\in V\), is a \(D\)-power of an automaton \(B\) if \(A_ v=B\) for every \(v\in V\) and \(\varphi_ v(a,x)\) is independent of any \(\pi_ u(a)\) for every \((u,v)\notin E\). Given a class \({\mathcal D}\) of directed graphs. Then an automaton \(A\) is a \({\mathcal D}\)-power of \(B\) if it is a \(D\)-power of \(B\) for some \(D\in{\mathcal D}\). It is proved: Let \({\mathcal D}\) be a class of directed graphs which contains a strongly connected directed graph of order at least \(n\) for every \(n\geq 1\). Then every automaton can be isomorphically simulated by a \({\mathcal D}\)-power of the two-state automaton.