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.
What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?
algorithms;regular languages;automata;finite automata;regular expressions