Sheila A. Greibach

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.

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)).

• Forme normale de Greibach
• Famille abstraite de langages
• Greibach's theorem (en)