Sheila Greibach facts for kids

Sheila Adele Greibach (born 6 October 1939 in New York City) is an American scientist. She studies how computers understand and process information. Her work focuses on areas like formal languages (the rules computers use), automata (simple computer models), and compiler theory (how computer programs are translated).

She is a retired professor of Computer Science at the University of California, Los Angeles. Sheila Greibach is known for her work with other scientists, Seymour Ginsburg and Michael A. Harrison. They studied how to understand complex computer language rules using a model called a stack automaton. She also created a special way to write computer language rules, called the Greibach normal form, in 1965. She also looked into how different computer language rules work and if certain computer problems can be solved.

Early Life and Education

Sheila Greibach was a brilliant student. She earned her first degree with highest honors in 1960. She studied Linguistics (the study of language) and Applied Mathematics at Radcliffe College. Two years later, she earned her master's degree.

In 1963, she received her PhD from Harvard University. Her PhD project was about how computer languages are built. She continued working at Harvard until 1969. Then, she moved to the UCLA, where she became a professor. Her research interests include how computers work, how complex computer problems are, and how computer programs are designed.

Key Contributions to Computer Science

Sheila Greibach has taught many students, including Ronald V. Book and Michael J. Fischer. Her work has greatly influenced the field of computer science. She has written many important papers and helped us understand how computers process information.

Understanding Computer Languages

One of her important works is about "Jump PDA's." This research helped explain how certain types of computer languages, called "deterministic context-free languages," can be understood by computers very quickly. It showed that these languages can be processed by a specific kind of simple computer model called a "Pushdown automaton" with "jumps." This means computers can jump to different parts of a program's instructions.

She also studied "W-grammars," which are rules for computer languages. Her research explored how different limits on these rules affect the languages they can describe. This helped scientists understand how complex computer languages like ALGOL 68 are built.

In 1969, she published a paper called "An Infinite Hierarchy of Context-Free Languages." This paper showed that there are many different levels of complexity for a type of computer language called "context-free languages."

Another key paper from 1965 was "A New Normal-Form Theorem for Context-Free Phrase Structure Grammars." This is where she introduced the Greibach normal form. This is a standard way to write down the rules for context-free languages, making them easier to study and use.

She also showed that it's impossible for a computer to always tell if a given "context-free language" is a simpler type called a "linear context-free language." This is known as "The Unsolvability of the Recognition of Linear Context-Free Languages."

Teamwork and Research

Sheila Greibach often worked with other scientists. Here are some examples of her collaborative research:

• "Multitape AFA" (with Seymour Ginsburg, 1972): This paper explored how different types of computer models, called "automata," work when they have multiple "tapes" to store information.
• "Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem" (with E. P. Friedman, 1980): This research looked at a specific type of "Pushdown Automaton" and found that it was possible to solve certain problems related to them.
• "Stack automata and compiling" (with Seymour Ginsburg and Michael A. Harrison, 1967): This paper introduced the "stack automaton" as a mathematical model for how computer programs are translated. It helped explain how compilers (programs that translate code) work.
• "Quasi-realtime languages" (with Ronald V. Book, 1969): This work studied languages that can be processed very quickly by a type of computer model called a "Turing machine."
• "One-way stack automata" (with Seymour Ginsburg and Michael A. Harrison, 1967): This paper looked at how "one-way stack automata" process information and what kinds of operations they can perform.
• "Tape- and time-bounded Turing acceptors and AFLs" (with Ronald V. Book and Ben Wegbreit, 1970): This research explored how the amount of time and memory a computer uses affects the types of languages it can understand.
• "Uniformly erasable AFL" (with Seymour Ginsburg and Jonathan Goldstine, 1972): This paper showed that many well-known families of computer languages have a special property related to how they can be simplified.

In 1964, she also wrote about "Formal parsing systems." This paper discussed how computers can automatically understand the structure of sentences, which is important for both understanding human languages and translating computer code.

See also

• Greibach normal form
• Abstract family of acceptors
• Greibach's theorem