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.

Sheila Greibach
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

Notes et références
  1. (en) « Sheila A. Greibach », sur le site du Mathematics Genealogy Project.
  2. Page personnelle de Sheila A. Greibach.
  3. 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).
  4. 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).
  5. Sheila A. Greibach, « The Hardest Context-Free Language », SIAM J. Comput., vol. 2, no 4,‎ , p. 304-310 (DOI 10.1137/0202025).
  6. (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
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.