🚀 go-pugleaf

In article <170@eos.UUCP> jaw@eos.UUCP (James A. Woods) writes:
 >From article <773@uwm-cs.UUCP>, by litow@uwm-cs.UUCP (Dr. B. Litow):
 >> 
 >> .... Fairly recently two (I believe)
 >> Japanese computer scientists showed that star height 1 is decidable but
 >> the general problem is open. 
 >
 >I remember sitting in the office of U. C. Berkeley Professor John Rhodes
 >(of Krohn-Rhodes semigroup theorem fame) in the seventies, when,
 >in came a grad student claiming to have figured out star height.
 >Rhodes quipped that if this fellow indeed had the complexity of star height
 >down pat -- he'd give him a doctorate on the spot.
 >
 >(You'll smile if you know the history of Rhodes' own Ph.D.)
 >
 >Anyway, maybe that degree has been awarded.

More recently (1986 or 1987), Dr. Hashigushi has reported a solution to the
general problem. That is, to decide the star height of a regular expression.
This work will appear in "Information and Computation". It is pretty dense.

By the way, which is the history about Rhodes' own Ph.D. (to :-)?


--
rabaeza@waterloo.csnet         1-519-885-1211 x6709    Ricardo Baeza-Yates
rabaeza%waterloo@csnet-relay.arpa                      CS Dept., U. Waterloo 
{allegra,decvax,ihnp4,utzoo}!watmath!watmum!rabaeza    Waterloo, Ont. N2L3G1