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?

|cite|improve this question
$\endgroup$
  • 1
    $\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
  • 9
    $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.