Alon et al. (1991):

The work by Alon et al. (1991) (http://www.dlsi.ua.es/~mlf/nnafmc/papers/alon91efficient.pdf) stems from the following consideration: if $n_X$ TLUs may be found in $2^{n_X}$ different states, ``one might wonder if an $\vert Q\vert$-state FSM could be implemented in a network with $O(\log \vert Q\vert)$ nodes''. These authors set out to establish bounds on the smallest number of TLU needed to implement a binary Mealy machine, that is, a Mealy machine with binary input and output alphabets ( $\Sigma=\Gamma=\{0,1\}$), using a single-layer first-order DTRNN architecture which is basically a neural Moore machine (section 3.2.2) with threshold linear units. The results are far above the optimistic $O(\log \vert Q\vert)$. The main result presented by Alon et al. (1991) is that the number of units necessary to implement a $\vert Q\vert$-state Mealy machine in such an architecture is $\Omega((\vert Q\vert\log \vert Q\vert)^{1/3})$ (lower bound to the complexity) and $O((\vert Q\vert)^{3/4})$ (upper bound to the complexity) when no restrictions whatsoever are imposed on the fan-in or the fan-out of the units or on the values of weights. To obtain the lower bound, they use a counting argument based on a lower bound on the number of ``really different'' Mealy machines of $\vert Q\vert$ states and a lower bound on the number of different Mealy machines that may be built using $n_X$ or less TLU. The upper bound is obtained by construction but details are not given in the current paper. However, reasonable (``mild'') restrictions on fan-ins, fan-outs and weights lead to equal upper ($O(\vert Q\vert)$) and lower ($\Omega(\vert Q\vert)$) bounds.