20
$\begingroup$

There are several papers in the literature that refer to the Pumping Lemma for context free languages as Bar-Hillel's Lemma (for example, here, here, and on the Wikipedia page). However, the first article to prove the result was only co-authored by Bar-Hillel:

Y. Bar-Hillel, M. Perles, E. Shamir. On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14:143–172, 1961.

Is there a good reason the result is sometimes called Bar-Hillel's Lemma, or is it simply a mis-attribution?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ For what it's worth, the Wikipedia entry for Bar-Hillel states the following: "In 1953, he founded a pioneering algebraic-computational linguistic group, and in 1961 he contributed to the proof of the pumping lemma for context-free languages (sometimes called the Bar-Hillel lemma)." (emphasis mine) $\endgroup$
    – Clement C.
    Jun 3 '17 at 17:09
  • 11
    $\begingroup$ There are some recent slides by Eli Shamir here (mps2016.labri.fr/archives/shamir.pptx) that include this paper. It's hard to know what words went along with the slides, but they do mention that Perles and Shamir were PhD students in math at the time, whereas Bar-Hillel was a professor who already had an established record in algebraic linguistics (dtic.mil/dtic/tr/fulltext/u2/400604.pdf). This is just speculation, but perhaps the reason the lemma got attached to Bar-Hillel's name had to do with the asymmetric relationship of the three coauthors? $\endgroup$
    – Noam Zeilberger
    Jun 4 '17 at 7:17
  • 1
    $\begingroup$ Also, it happens sometimes that the authors disclose to which of them some lemma/theorem is due to, see for example the Lovasz Local Lemma from Erdős, Paul; Lovász, László: Problems and results on 3-chromatic hypergraphs and some related questions - in this case it was Erdos who wanted to make it clear that the lemma was entirely Lovasz's. $\endgroup$
    – domotorp
    Apr 4 '19 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.