1973/12/01 by C.P. Pfleeger, Charles P. Pfleeger
Computer Science · #Machine Learning and Algorithms #Computability, Logic, AI Algorithms #Neural Networks and Applications
paper · doi:10.1109/t-c.1973.223655
The problem of reducing the number of states in an arbitrary incompletely specified deterministic finite-state machine to k states (for a given k) has proven intractible to solution within "reasonable" time; most techniques seem to require exponential time. Two reduction techniques–state assignment to the DON'T CARE entries, and so-called "state splitting"–are investigated. For both of the techniques, the question, "Can I achieve an equivalent k state machine?" is shown to be polynomial complete, with the resulting conjecture that neither is solvable in time bounded by a polynomial function of the size of the machine.