The Pumping Lemma for context-free languages, a fundamental tool in theoretical computer science used to demonstrate that specific languages lack context-free properties, was identified by Micha Perles in collaboration with Yehoshua Bar-Hillel and Eli Shamir. This discovery remains a standard method for researchers analyzing the boundaries of formal language theory and computational complexity.
Academic Foundation and Career
Born in Jerusalem in 1936, Micha Asher Perles completed his doctoral studies at the Hebrew University of Jerusalem. He earned his Ph.D. in 1964 under the academic supervision of Branko Grünbaum. Throughout his career, Perles maintained a long-term affiliation with the Hebrew University of Jerusalem, where he eventually reached the status of professor emeritus. His professional contributions encompass the fields of combinatorics, graph theory, and geometry.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Contributions to Geometry and Set Theory
Perles developed the Perles configuration, which consists of a set of nine specific points located within the Euclidean plane. This configuration demonstrates that collinearities can only be realized when irrational numbers are employed as coordinates. He utilized this finding to establish the existence of irrational polytopes within higher dimensions. Additionally, his work in extremal set theory includes the Perles–Sauer–Shelah lemma, a mathematical result for which Saharon Shelah formally credited Perles with the proof.
Mentorship and Influence
As an educator, Perles guided the development of several scholars who went on to make significant impacts in the mathematical sciences. Among his most notable students are Noga Alon, Gil Kalai, and Nati Linial. His work at the Hebrew University of Jerusalem ensured that his methods in combinatorics and geometry were passed to subsequent generations of researchers.
Fast facts
- Born: 1936, Jerusalem
- Citizenship: Israel
- Occupation: Mathematician and university teacher
- Doctoral advisor: Branko Grünbaum
- Ph.D. year: 1964
- Primary fields: Combinatorics, graph theory, geometry
Questions readers ask
What is the primary significance of the Perles configuration?
It is a set of nine points in the Euclidean plane requiring irrational coordinates to realize its collinearities, which Perles used to prove the existence of irrational polytopes in higher dimensions.
With whom did Micha Perles develop the pumping lemma?
He developed the pumping lemma for context-free languages alongside Yehoshua Bar-Hillel and Eli Shamir.
Achievements
- Held posts at Hebrew University of Jerusalem
- Fields: combinatorics and graph theory
