Let K(m) be the smallest number with the property that every m-state Mealy machine can be built as a threshold machine using K(m) or fewer threshold cells. The authors propose the use of K(m) as a measure of the power of the threshold machine model and their lower bounds on K(m) as an indication of the model’s weakness. Using an elegant construction of Mealy machines and simple but effective counting arguments on threshold machines, they prove that K ( m ) = &OHgr; ( ( m log m ) ^⅓ ). Similar counting arguments have appeared in Cameron [1] and Muroga [2]. Dewdney [3] has previously shown that K ( m ) = O ( m ^¾ ).

The authors consider certain restrictions of the threshold machine model that might arise in practice. If the weights of the threshold cells are drawn from a finite set or if the fan-out of the cells is restricted to a constant, then K ( m ) = &OHgr; ( ( m log m ) ^½ ). If the fan-in of the cells is restricted to a constant, then K ( m ) = &OHgr; ( m ). Similarly, if the fan-out of the cells is restricted to a constant and the weights and threshold values are drawn from a finite set, then K ( m ) = &OHgr; ( m ).

The paper ends with a proof by construction that every m-state Mealy machine can be simulated by a 2 m + 1 cell threshold machine with a finite weight and threshold set. The paper is well written and, except for the last construction, easy to read.