A general model of a memory-based finite-state machine architecture is introduced, the 2k− decision machine (2k− D). The classical (2n− D) and binary decision (2 − D) architectures are shown to be special cases of the 2k− D architecture. The equivalence among the 2k− D solutions for different values of k follows from the sequentialization principle, which is stated in the paper. A cost measure is defined in terms of memory size and a procedure to determine the 2k− D architecture which offers the minimum cost, given that the speed is equal to one state transition per clock cycle, is presented. It is shown that this architecture is not in general the minimum cost solution when the speed of the circuit is not a critical design factor. Also discussed, are the optimization problems to be solved when a minimum cost 2k− D architecture is desired. In addition, bounds on the cost of the 2k− D architecture are calculated in terms of simple measures taken from the mathematical model describing the behavior of the state machine. The results of this research are particularly attractive when LSI and VLSI technologies are considered. State machines constitute fundamental blocks in systems to be fabricated as integrated circuits. Memory-based implementations offer a short design time, regularity of structure, and expandability.