Sheila Greibach


Sheila Adele Greibach is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los Angeles, and notable work include working with Seymour Ginsburg and Michael A. Harrison in context-sensitive parsing using the stack automaton model.
Besides establishing the normal form for context-free grammars, in 1965, she also investigated properties
of W-grammars, pushdown automata, and decidability problems.

Early career

Greibach earned an A.B. degree in Linguistics and Applied Mathematics from Radcliffe College in 1960, and two years after achieved an A.M. degree. In 1963, she was awarded a PhD at Harvard University, advised by Anthony Oettinger with a PhD thesis entitled "Inverses of Phrase Structure Generators".
She continued to work at Harvard at the Division of Engineering and Applied Physics until 1969 when she moved to UCLA, where she has been a professor until present.

Work and contributions

Among her students were Ronald V. Book and Michael J. Fischer.
The following list indicates some of her work. The top portion of the list is from the and the remainder from the by David M. Jones.

From ACM Digital Library

"Jump PDA's, deterministic context-free languages, principal AFDLs and polynomial time recognition," Proceedings of the fifth annual ACM symposium on Theory of Computing, April 1973
"Some restrictions on W-grammars"
Proceedings of the sixth annual ACM symposium on Theory of computing, April 1974
"An Infinite Hierarchy of Context-Free Languages," Journal of the ACM, Volume 16 Issue 1, January 1969
"A New Normal-Form Theorem for Context-Free Phrase Structure Grammars," JACM, Volume 12 Issue 1, January 1965
"The Unsolvability of the Recognition of Linear Context-Free Languages," JACM, Volume 13 Issue 4, October 1966

Co-authored works

"Multitape AFA," co-authored with Seymour Ginsburg, Journal of the ACM, Volume 19 Issue 2, April 1972
"Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem", co-authored with E. P. Friedman, "JACM", October 1980, Volume 27 Issue 4
"Stack automata and compiling," co-authored with Seymour Ginsburg and Michael A. Harrison, "JACM", January 1967, Volume 14 Issue 1
"Quasi-realtime languages," co-authored with Ronald V. Book, Proceedings of the first annual ACM symposium on Theory of Computing, May 1969
"One-way stack automata," co-authored with Seymour Ginsburg and Michael A. Harrison, "JACM", April 1967, Volume 14 Issue 2
"Tape- and time-bounded Turing acceptors and AFLs "
co-authored with Ronald V. Book and Ben Wegbreit, Proceedings of the second annual ACM symposium on Theory of computing, May 1970
"Uniformly erasable AFL", co-authored with Seymour Ginsburg and Jonathan Goldstine, Proceedings of the fourth annual ACM symposium on Theory of computing, May 1972
;Formal parsing systems

Others