Finite automata

The networks discussed in the main text can be viewed as finite automata (also known as finite state machines). Each node in the network corresponds to a state in the automaton, and each arc represents a transition that occurs when a particular value is given as input. NetCAStep above in general produces a non-deterministic finite automaton (NDFA) for which a particular sequence of values does not determine a unique path through the network. MinNet creates an equivalent DFA, then minimizes this. The Myhill–Nerode theorem ensures that a unique minimal DFA can always be found (though to do so is in general a PSPACE-complete problem).

The total number of distinct minimal finite automata with k = 2 possible labels for each arc grows with the number of nodes as follows: 3, 7, 78, 1388, ... (The simple result (n + 1)^{n k} based on the number of ways to connect up n nodes is a significant overestimate because of equivalence between automata with different patterns of connections.)