Issue No.08 - August (1975 vol.24)
F. Rubin , System Development Division, IBM Corporation Poughkeepsie
An exact upper bound is found for the number of maximal compatible subsets of an n-state incompletely specified sequential machine (ISSM). This bound, on the order of 3n/3, iS also a worst case computer storage and computation time limit for any algorithm to find maximal compatibles.
Incompatibility graph, incompletely specified sequential machine (ISSM), maximal compatible, state mninimization, worst case bound.
F. Rubin, "Worst Case Bounds for Maximal Compatible Subsets", IEEE Transactions on Computers, vol.24, no. 8, pp. 830-831, August 1975, doi:10.1109/T-C.1975.224315