Sheila Adele Greibach (born 6 October 1939 in New York City) is an American 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 (Greibach normal form) for context-free grammars, in 1965, she also investigated properties
of W-grammars, pushdown automata, and decidability problems.
Greibach earned an A.B. degree (summa cum laude) 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 the present (as of March 2014). Her areas of interest and research include Theoretical computer science, Computational complexity, Program schemes and semantics, Formal language, Automata, and Computability.
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 ACM Digital Library and the remainder from the FOCS Bibliography by David M. Jones.
"Jump PDA's, deterministic context-free languages, principal AFDLs and polynomial time recognition (Extended Abstract)," Proceedings of the fifth annual ACM symposium on Theory of Computing, April 1973
Every deterministic context-free language can be accepted by a deterministic finite delay pda with jumps. Increasing the number of types or occurrences of jumps increases the family of languages accepted with finite delay. Hence the family of deterministic context-free language is a principal AFDL; there is a context-free language
such that every context-free language is an inverse gsm image of
"Some restrictions on W-grammars"
Proceedings of the sixth annual ACM symposium on Theory of computing, April 1974
The effect of some restrictions on W-grammars (the formalization of the syntax of ALGOL 68) are explored. Two incomparable families examined at length are WRB (languages generated by normal regular-based W-grammars) and WS (languages generated by simple W-grammars). Both properly contain the context-free languages and are properly contained in the family of quasirealtime languages. In addition, WRB is closed under nested iterate ...
"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
The problem of whether a given context-free language is linear is shown to be recursively undecidable.
"Multitape AFA," co-authored with Seymour Ginsburg, Journal of the ACM, Volume 19 Issue 2, April 1972