On networks of non-deterministic automata.
Karl-Adolf Zech · Czech digital mathematics library · 1976
In the present paper it is shown that in the structure theory of non-deterministic automata (NDA) it is sufficient to consider only two standard network forms.The conditions are stated under which an NDA can be isomorphically embedded in a network of smaller NDA's with proper output.It turns out that every finite NDA has a decomposition into a network of this type.Finally, the conditions for the existence of a decomposition the components of which realize the network output are derived.The results are stated and proved for the special case of two-component networks.* We use the symbol P(5) to denote the set of all subsets of the set S while the asterisk means that the empty subset is omitted.