Sheila A. Greibach
Sheila Adele Greibach, née le à New York City), est une informaticienne théoricienne et chercheuse universitaire américaine, notamment en théorie des langages formels, théorie des automates, théorie de la compilation. Elle est professeur émérite en informatique à l'Université de Californie à Los Angeles.
| Naissance |
New York City, New York, États-Unis |
|---|---|
| Nationalité | américaine |
| Domaines | Informatique théorique,Théorie des langages, Automates, Théorie de la complexité, Théorie de la compilation |
|---|---|
| Institutions | Université de Californie à Los Angeles |
| Diplôme | Ph. D. |
| Formation | Radcliffe College, Université Harvard |
| Directeur de thèse | Anthony Oettinger |
| Étudiants en thèse | Ronald V. Book, Michael J. Fischer, Jean Henri Gallier, Steven Lindell, Jose Rolim, Detlef Wotschke[1] |
| Renommé pour | Forme normale de Greibach, « hardest language » |
Biographie professionnelle
Sheila Greibach obtient un A. B. au Radcliffe College en Linguistique et Mathématiques appliquées avec la mention summa cum laude en 1960, et un A. M. en 1962 au même collège. En 1963, elle termine un Ph. D. à l'Université Harvard, sous la direction d'Anthony Oettinger[1]. Le titre de sa thèse est « Inverses of Phrase Structure Generators ».
Jusqu'en 1969, elle travaille à Harvard, dans la Division of Engineering and Applied Physics[2]. Elle rejoint alors l'Université de Californie à Los Angeles, où elle est professeur depuis 1970.
Recherche
Sheila Greibach a travaillé avec Seymour Ginsburg et Michael A. Harrison sur la théorie des langages formels, les grammaires formels, et les variétés de modèles d'automate à pile. Un de ses résultats les plus connus, établi en 1965, est la mise sous forme particulière des grammaires non contextuelles appelée la forme normale de Greibach[3]. Elle a aussi travaillé sur des problèmes de décision, les grammaires de Van Wijngaarden (en) ou W-grammaires, les automates à pile, les langages algébriques déterministes[4], la complexité de reconnaissance[5]. Elle a eu comme élève notamment Ronald V. Book et Michael J. Fischer[1]. Elle est auteur d'un livre sur la sémantique des langages de programmation[6], réédité en 2005 en livre électronique ( (ISBN 978-3-540-37942-3)).
Articles liés
- Forme normale de Greibach
- Famille abstraite de langages
- Greibach's theorem (en)
Notes et références
- (en) « Sheila A. Greibach », sur le site du Mathematics Genealogy Project.
- Page personnelle de Sheila A. Greibach.
- Sheila A. Greibach, « A New Normal-Form Theorem for Context-Free Phrase Structure Grammars », Journal of the ACM, vol. 12, no 1,‎ , p. 42-52 (DOI 10.1145/321250.321254).
- Seymour Ginsburg et Sheila Greibach, « Deterministic context free languages », Information and Control, vol. 9, no 6,‎ , p. 620-648 (DOI 10.1016/s0019-9958(66)80019-0).
- Sheila A. Greibach, « The Hardest Context-Free Language », SIAM J. Comput., vol. 2, no 4,‎ , p. 304-310 (DOI 10.1137/0202025).
- (en) Sheila A. Greibach, Theory of program structures : schemes, semantics, verification, Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science, vol. 36 », , 389 p. (ISBN 0-387-07415-5, SUDOC 016891988).
Liens externes
- « Page personnelle de Sheila A. Greibach », Université de Californie à Los Angeles
- Ressources relatives à la recherche :