Publication
Journal of Computer and System Sciences
Paper

Frequency of decomposability among machines with a large number of states

View publication

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.

Date

01 Oct 1968

Publication

Journal of Computer and System Sciences

Authors

Topics

Share