Sheila Greibach
Encyclopedia
Sheila Adele Greibach is a researcher in formal language
s, automata
,
compiler
theory in particular; and computer science
in general. She is currently Professor of Computer Science
at the University of California, Los Angeles.
She worked with Seymour Ginsburg
and Michael Harrison in context-sensitive parsing using the stack automaton model.
Besides establishing the normal form (Greibach normal form
) for context-free grammar
s now named after her, in 1965, she also investigated properties
of W-grammars, pushdown automata, and decidability problems.
in linguistics and applied mathematics (summa cum laude), and subsequently her A.M. degree in 1962. In 1963, she achieved her Ph.D. at Harvard University
, under the auspices of Anthony Oettinger. The title of her PhD thesis is
"Inverses of Phrase Structure Generators".
She continued to work at Harvard at the Division of Engineering and Applied Physics, until she changed in 1969 to the University of California in Los Angeles (UCLA), where she has been professor since 1970 until present, as of May 2011.
Multitape AFA
Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem
Stack automata and compiling
Quasi-realtime languages (Extended Abstract)
One-way stack automata
Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract)
Some restrictions on W-grammars
Uniformly erasable AFL
Formal parsing systems
An Infinite Hierarchy of Context-Free Languages
A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
The Unsolvability of the Recognition of Linear Context-Free Languages
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s, automata
Automata
Automata is the plural form of automaton, a self-operating machine. It may also refer to:* "Automata", a short story by E. T. A. Hoffmann* "Automata", a hardboiled science fiction crime series by Penny Arcade...
,
compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
theory in particular; and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
in general. She is currently Professor of Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at the University of California, Los Angeles.
She worked with Seymour Ginsburg
Seymour Ginsburg
Seymour Ginsburg was a pioneer of automata theory, formal language theory, anddatabase theory, in particular; and computer science, in general...
and Michael Harrison in context-sensitive parsing using the stack automaton model.
Besides establishing the normal form (Greibach normal form
Greibach normal form
In computer science and formal language theory, a context-free grammar is in Greibach normal form if the right-hand sides of all productions start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty...
) for context-free grammar
Context-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
s now named after her, in 1965, she also investigated properties
of W-grammars, pushdown automata, and decidability problems.
Early life
In 1960 she earned her A.B. degree from Radcliffe CollegeRadcliffe College
Radcliffe College was a women's liberal arts college in Cambridge, Massachusetts, and was the coordinate college for Harvard University. It was also one of the Seven Sisters colleges. Radcliffe College conferred joint Harvard-Radcliffe diplomas beginning in 1963 and a formal merger agreement with...
in linguistics and applied mathematics (summa cum laude), and subsequently her A.M. degree in 1962. In 1963, she achieved her Ph.D. at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
, under the auspices of Anthony Oettinger. The title of her PhD thesis is
"Inverses of Phrase Structure Generators".
She continued to work at Harvard at the Division of Engineering and Applied Physics, until she changed in 1969 to the University of California in Los Angeles (UCLA), where she has been professor since 1970 until present, as of May 2011.
Work and Contributions
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.From ACM Digital Library
Jump PDA's, deterministic context-free languages, principal AFDLs and polynomial time recognition (Extended Abstract)- Sheila A. Greibach
- April 1973
- Proceedings of the fifth annual ACM symposium on Theory of computing
- Every deterministic context-free languageDeterministic context-free languageA deterministic context-free language is a formal language which is defined by a deterministic context-free grammar. The set of deterministic context-free languages is called DCFL and is identical to the set of languages accepted by a deterministic pushdown automaton.The set of deterministic...
can be accepted by a deterministic finite delay pdaPushdown automatonIn automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data.- Operation :Pushdown automata differ from finite state machines in two ways:...
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 
or 
.
Multitape AFA
- Seymour Ginsburg, Sheila Greibach
- April 1972
- Journal of the ACM (JACM), Volume 19 Issue 2
Superdeterministic PDAs: A Subcase with a Decidable Inclusion problem
- S. A. Greibach, E. P. Friedman
- October 1980
- Journal of the ACM (JACM), Volume 27 Issue 4
Stack automata and compiling
- Seymour Ginsburg, Sheila A. Greibach, Michael A. Harrison
- January 1967
- Journal of the ACM (JACM), Volume 14 Issue 1
- Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursi ...
Quasi-realtime languages (Extended Abstract)
- Ronald V. Book, Sheila A. Greibach
- May 1969
- Proceedings of the first annual ACM symposium on Theory of computing
- Quasi-realtime languages are the languages accepted by nondeterministic multitape Turing machineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a non-deterministic one stack, one pushdown store machine, and can be e ...
One-way stack automata
- Seymour Ginsburg, Sheila A. Greibach, Michael A. Harrison
- April 1967
- Journal of the ACM (JACM), Volume 14 Issue 2
- A number of operations which either preserve sets accepted by one-way stack automata or preserve sets accepted by deterministic one-way stack automata are presented. For example, sequential transduction preserves the former; set complementation, the latter. Several solvability questions are also considered.
Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract)
- Ronald V. Book, Sheila A. Greibach, Ben Wegbreit
- May 1970
- Proceedings of the second annual ACM symposium on Theory of computing
- Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied with the aim of showing sufficient conditions for these classes to be AFLs and to be principal AFLs.
Some restrictions on W-grammars
- Sheila A. Greibach
- April 1974
- Proceedings of the sixth annual ACM symposium on Theory of computing
- The effect of some restrictions on W-grammars (the formalization of the syntax of ALGOL 68ALGOL 68ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...
) 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 ...
Uniformly erasable AFL
- Sheila Carlyle-Greibach, Seymour Ginsburg, Jonathan Goldstine
- May 1972
- Proceedings of the fourth annual ACM symposium on Theory of computing
- The purpose of this paper is to show that a number of well-known families have property (*). In particular, we prove that the family of context-free languages does indeed have this property. In addition, we show that several familiar subfamilies of the context-free languages, such as the one-counter languages, have property (*). Finally, we show that there are families satisfying (*) which are not subfamilies of the context-free languages, for we prove that any family generated from one-let ...
Formal parsing systems
- Sheila A. Greibach
- August 1964
- Communications of the ACM, Volume 7 Issue 8
- Automatic syntactic analysis has recently become important for both natural languageNatural languageIn the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...
data processing and syntax-directedSyntax-directed translationIn computer programming, Syntax-directed translation is a method of translating a string into a sequence of actions by attaching one such action to each rule of a grammar. Thus, parsing a string of the grammar produces a sequence of rule applications...
compilers. A formal parsing system G = (V, &mgr;, T, R) consists of two finite disjoint vocabularies, V and T, a many-many map, &mgr;, from V onto T, and a recursive set R of strings in T called syntactic sentence classes ...
An Infinite Hierarchy of Context-Free Languages
- Sheila A. Greibach
- January 1969
- Journal of the ACM (JACM), Volume 16 Issue 1
A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- Sheila A. Greibach
- January 1965
- Journal of the ACM (JACM), Volume 12 Issue 1
The Unsolvability of the Recognition of Linear Context-Free Languages
- Sheila A. Greibach
- October 1966
- Journal of the ACM (JACM), Volume 13 Issue 4
- The problem of whether a given context-free language is linear is shown to be recursively undecidable.
From FOCS Bibliography
- Seymour Ginsburg and Sheila Greibach.
- Deterministic context free languages.
- In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 203-220. IEEE, 1965.
- Seymour Ginsburg, Sheila A. Greibach, and Michael A. Harrison.
- One-way stack automata (extended abstract).
- In Conference Record of 1966 Seventh Annual Symposium on Switching and Automata Theory, pages 47-52, Berkeley, California, 26–28 October 1966. IEEE.
- Sheila A. Greibach.
- An infinite hierarchy of context-free languages.
- In Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, pages 32-36, Austin, Texas, 18–20 October 1967. IEEE.
- Seymour Ginsburg and Sheila Greibach.
- Abstract families of languages.
- In Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, pages 128-139, Austin, Texas, 18–20 October 1967. IEEE. Citations.
- Sheila Greibach.
- Checking automata and one-way stack languages (extended abstract).
- In Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, pages 287-291, Schenectady, New York, 15–18 October 1968. IEEE. Citations.
- Sheila A. Greibach.
- Full AFLs and nested iterated substitution.
- In Conference Record of 1969 Tenth Annual Symposium on Switching and Automata Theory, pages 222-230, Waterloo, Ontario, Canada, 15–17 October 1969. IEEE.
- J. W. Carlyle, S. A. Greibach, and A. Paz.
- A two-dimensional generating system modeling growth by binary cell division (preliminary report).
- In 15th Annual Symposium on Switching and Automata Theory, pages 1-12, The University of New Orleans, 14–16 October 1974. IEEE.
- S. A. Greibach.
- Formal languages: Origins and directions.
- In 20th Annual Symposium on Foundations of Computer ScienceSymposium on Foundations of Computer ScienceFOCS, the Annual IEEE Symposium on Foundations of Computer Science, is an academic conference in the field of theoretical computer science...
, pages 66-90, San Juan, Puerto Rico, 29–31 October 1979. IEEE.
Others
- Ronald Book, Shimon Even, Sheila Greibach and Gene Ott.
- Ambiguity in Graphs and Expressions.
- IEEE Transactions on Computers, vol. c-20, No. 2, February 1971. IEEE.