Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!utcsri!arvind From: arvind@utcsri.UUCP Newsgroups: ut.theory Subject: THEORY NET: RE: Minimal number of states ... Message-ID: <5471@utcsri.UUCP> Date: Tue, 29-Sep-87 10:44:43 EDT Article-I.D.: utcsri.5471 Posted: Tue Sep 29 10:44:43 1987 Date-Received: Wed, 30-Sep-87 03:05:56 EDT Distribution: ut Organization: CSRI, University of Toronto Lines: 30 Date: 28 Sep 1987 10:53:28-EDT (Monday) From: 'Steve' Stevenson Subject: Re: Minimal number of states for finite state machine in article , steve@hubcap.clemson.EDU ("Steve" Stevenson) > > Is there an efficient algorithm for converting a finite state machine into > an equivalent machine with a minimal number of states? You may choose the > objective function. Unfortunately, the original posting was unclear as to what I wanted. I'm looking for the absolute minimum and hence either deterministic ^^^^^^^^^^^^^^^^ or nondeterministic, whichever is smaller. The below seems to answer the query. Thanks to all who responded. >If the finite state machine is deterministic, there are standard, >O(n sup 2) algorithms for state minimization; see Hopcroft and Ullman, >"Introduction to Automata Theory, Languages, and Computation," >Addison-Wesley, 1979. If the finite state machine is nondeterministic, >the proble is PSPACE-complete; >see Garey and Johnson, "Computers and Intractability," W.H. Freeman, 1979. > >David Johnson, AT&T Bell Laboratories -- Steve (really "D. E.") Stevenson steve@hubcap.clemson.edu Department of Computer Science, (803)656-5880.mabell Clemson University, Clemson, SC 29634-1906