Encoding of Asynchronous Sequential Networks

This paper is intended to improve Huffman´s results on universal encoding of asynchronous sequential networks. The method employed here consists of assigning to each row of the flow table a single vertex on the corresponding hypercube. The remaining vertices are used for the transitions between stable states. Such a vertex can be used for different transitions if they correspond to distinct input states. In order to verify that an assignment is universal, we have to generate all possible structures of columns (all partitions of the set of vertices assigned to the rows). Then, we have to verify that the chosen assignment is compatible with all these partitions. An assignment will be compatible with the structure of a column if 1) the elements of a block are connected by transient sequences of adjacent values of the internal variable; 2) the transient sequences of two distinct blocks have no common element. Interesting solutions that cannot be further improved are found for 7- and 8-row flow tables. For 12-row flow tables the use of a computer is indispensable. A solution of 5 components of the internal variable is proposed.