Sheila Greibach
| Sheila Greibach | |
| Született | 1939. október 6. (85 éves)[1] New York[2] |
| Állampolgársága | amerikai |
| Foglalkozása |
|
| Iskolái |
|
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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]- Theory of Program Structures: Schemes, Semantics, Verification (Lecture Notes in Computer Science), Springer, 1975, 2005, 2014.
Cikkek (válogatás)
[szerkeszté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)
Jegyzetek
[szerkesztés]- ↑ Integrált katalógustár (Németotszág) (német nyelven). (Hozzáférés: 2014. április 9.)
- ↑ Integrált katalógustár (Németotszág) (német nyelven). (Hozzáférés: 2014. december 10.)
