1
$\begingroup$

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ascribes the algorithm to McNaughton and Yamada, who have indeed described it in their paper.

It might appear like a standard situation when one algorithm is ascribed to different authors. However, things seem to be more complicated. In fact, McNaughton and Yamada dealt with a converse problem (constructing a finite automaton to a rational expression) as well and Wikipedia's article on Thompson's construction refers to this algorithm as to the McNaughton-Yamada algorithm.

For this reason, I would like to ask what is the most correct name one can use for the Kleene/McNaughton-Yamada algorithm? In fact, I would also be interested in a correct name for a generalized algorithm, which works over arbitrary, say, complete (or closed, Conway, etc.) semirings. Thank you in advance.

P.S. Sorry for not providing a link to the McNaughton-Yamada paper, but I was not allowed to post more than 2 links.

$\endgroup$
3
  • $\begingroup$ Stigler's law of eponymy: "No scientific discovery is named after its original discoverer". The link contains some more interesting things, like "Boyer's Law". $\endgroup$ May 6, 2016 at 11:07
  • $\begingroup$ "... rational expressions ..." -- Did you mean "regular expressions"? $\endgroup$ May 6, 2016 at 11:09
  • $\begingroup$ @AntonTrunov Yes, regular expressions are the same thing (at least in this context). And as to the first comment: I am aware of this. However, there almost always is some name that seems preferable to the majority of the community. My question was aiming at such a name, although I might not phrased it clearly enough. $\endgroup$ May 6, 2016 at 11:12

1 Answer 1

1
$\begingroup$

There is no such thing as a "correct" name. There is the name that is commonly used, which might depend on the community. This is what you would use unless you want to make a point. If you think that the common name doesn't give credit to the right people, you can use a different name, though you should also mention the common name so that others know what theorem you refer to.

Mathematical theorems and concepts are often named not after the first people who proved or defined them (if you're interested, you should be able to find several lists of such theorems and concepts online). Yet once a name has stuck, it is different to change it. That is because the most important goal of a name is not to give credit but rather to give a short name for a common concept. Indeed, sometimes results are not named after anybody, even though many of them were first proved by somebody.

$\endgroup$
1
  • $\begingroup$ I definitely agree with this. However, although "correct" names might not exist in a strict sense, there certainly are some that are more correct than others (either because of common usage, or because of historical relevance). More precisely, I am looking for a name that is common enough, preferably unambiguous (in the sense that at least most people who know the name would associate it with the same thing) and reasonably correct in the historical sense. $\endgroup$ May 6, 2016 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.