Frequency of decomposability among machines with a large number of states

Abstract

In a universe of machines with n labeled states and p labeled inputs, it is shown that almost all machines have series-parallel decomposition if n and p approach infinity in such a way that pn1/2e-n→0. Also, almost all machines have no series-parallel decomposition if n and p approach infinity in such a way that pn1/6e-n→∞. © 1968 Academic Press Inc.