Frequency of decomposability among machines with a large number of states

摘要

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→∞.