Sheila Greibach

Sheila Greibach
Született	1939. október 6. (84 éves) New York
Állampolgársága	amerikai
Foglalkozása	informatikus egyetemi oktató
Iskolái	Harvard Egyetem Radcliffe College
Sablon • Wikidata • Segítség

Sheila Adele Greibach (New York, 1939. október 6. –) amerikai matematikus, informatikus, a formális nyelvek és automaták kutatója, egyetemi tanár. A környezetfüggetlen nyelvek egyik normálalakjának és egy eldönthetetlenségi tételnek a névadója.

Életpályája

1960-ban elvégezte a Radcliffe College alkalmazott matematika és nyelvészeti szakjait summa cum laude minősítéssel. 1963-ban doktorált a Harvard Egyetemen. 1969-ig a Harvardon dolgozott, majd átment a Los Angeles-i Kaliforniai Egyetemre, ahol 2014-ig tanított, amikor emeritus professor lett.

Seymour Ginsburg és Michael A. Harrison professzorokkal a formális nyelvek elméletével foglalkozott. 1965-ban írta le a környezetfüggetlen nyelvek róla elnevezett normálalakját. Foglalkozott eldönthetetlenségi problémákkal (egy ilyen tétel a nevét viseli), veremautomatákkal, W nyelvtanokkal (Van Wijngaarden típusú nyelvtanok) és bonyolultsági problémákkal.

Munkássága

Kutatási területei: algoritmusok és bonyolultságuk, programsémák és szemantika, formális nyelvek és automaták elmélete, kiszámíthatóság.

Könyv

• Theory of Program Structures: Schemes, Semantics, Verification (Lecture Notes in Computer Science), Springer, 1975, 2005, 2014.

Cikkek (válogatás)

• Sheila A. Greibach, Weiping Shi, Shai Simonson: Single Tree Grammars. Theoretical Studies in Computer Science 1992: 73-99
• José D. P. Rolim, Sheila A. Greibach: A Note on the Best-Case Complexity. Inf. Process. Lett. 30(3): 133-138 (1989)
• José D. P. Rolim, Sheila A. Greibach: On the IO-Complexity and Approximation Languages. Inf. Process. Lett. 28(1): 27-31 (1988)
• Sheila A. Greibach: Hierarchy Theorems for Two-Way Finite State Transducers. Acta Informatica 11: 80-101 (1978)
• Sheila A. Greibach:One Way Finite Visit Automata. Theoretical Computer Science 6: 175-221 (1978)
• Sheila A. Greibach: Remarks on Blind and Partially Blind One-Way Multicounter Machines. Theoretical Computer Science. 7: 311-324 (1978)
• Sheila A. Greibach: Remarks on the Complexity of Nondeterministic Counter Languages. Theoretical Computer Science 1(4): 269-288 (1976)
• Seymour Ginsburg, Jonathan Goldstine, Sheila A. Greibach: Some Uniformly Erasable Families of Languages. Theoretical Computer Science 2(1): 29-44 (1976)
• Sheila A. Greibach: A New Normal-Form Theorem for Context-Free Phrase Structure Grammars. Journal ACM 12(1): 42-52 (1965)
• Seymour Ginsburg, Sheila A. Greibach: Deterministic context free languages. SWCT (FOCS) 1965: 203-220
• Sheila A. Greibach: Formal parsing systems. Communication ACM 7(8): 499-504 (1964)
• Sheila A. Greibach: The Undecidability of the Ambiguity Problem for Minimal Linear Grammars. Information and Control 6(2): 119-125 (1963)

Források

• UCLA egyetemi honlap
• DBLP adatbázis