[Oops.] Misattribution of NFA->Regex algorithm

[plin25]

This is more for record-keeping than anything else, since a number of the details below were discovered by Jeff and conveyed to me during our private conversation about the misattribution.

In Section 4.8 of the Models notes, Jeff attributes the NFA->Regex algorithm to Han and Wood 2005. However, upon further inspection, Han and Wood did not come up with the algorithm; they cite Brzozowski and McCluskey 1963 (in fact the following diagram appears in their paper).

Kleene developed a similar idea in his 1951 paper (snapshot from the 1956 journal version below)

Of course, the formulation from Brzozowski and McCluskey 1963 is easily recognizable as being the same as the algorithm in Section 4.8, which is also the algorithm that appears in the popular Sipser 1997 book, whereas Kleene's version is not.

To make the matter even more confusing, a survey by Brzozowski 1962 attributes the algorithm to independent results by Naughton and Yamada 1960 and Lee 1960.

Naughton and Yamada 1960 indeed describe the algorithm in it's modern presentation

One observes readily that the recurrence that appears in Naughton and Yamada 1960 has the same recursive structure as the Floyd-Warshall algorithm, which, in Section 9.8 of the Algorithms text, Jeff attributes to Roy 1959 and (surprise!) Kleene 1951.

[plin25]

This is now fixed on the website, but not on Git