rabaeza@watmum.waterloo.edu (Ricardo Baeza) (02/05/88)
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