Sheila Greibach - Citizendia

Sheila Greibach (1939-) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. Year 1939 ( MCMXXXIX) was a Common year starting on Sunday (link will display the full calendar of the Gregorian calendar. A formal language is a set of words, ie finite strings of letters, or symbols. A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their She is currently Professor of Computer Science at the University of California, Los Angeles. Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their The University of California Los Angeles (generally known as UCLA) is a public research university located in Westwood Los Angeles, California, United

She worked with Seymour Ginsburg and Michael Harrison in context-sensitive parsing using the stack automaton model. Seymour Ginsburg (1928-2004 was a pioneer of Automata theory Formal language theory and Database theory in particular and Computer science In Computer science, a stack machine is a Model of computation in which the computer's memory takes the form of one or more stacks The term also refers

Besides establishing the normal form (Greibach normal form) for context-free grammars now named after her, in 1965, she also investigated properties of W-grammars, pushdown automata, and decidability problems. In Computer science, to say that a Context-free grammar is in Greibach normal form (GNF means that all production rules are of the form A \to \alpha In Formal language theory, a context-free grammar ( CFG) is a grammar in which every production rule is of the form V &rarr In Automata theory, a pushdown automaton (PDA is a finite automaton that can make use of a stack containing data In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on

1 Work and Contributions
2 See also

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 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 Lo such that every context-free language is an inverse gsm image of Lo or Lo - {e}.

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 machines 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 68) are explored. A Van Wijngaarden grammar (also vW-grammar or W-grammar) is a Two-level grammar which provides a technique to define potentially infinite Grammars Time-line of ALGOL 68 The Algorithmic Language ALGOL 68 Reports Mar 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 language data processing and syntax-directed 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. Events 306 - Maxentius is proclaimed Roman Emperor. 312 - Battle of Milvian Bridge: Constantine Year 1966 ( MCMLXVI) was a Common year starting on Saturday (link will display full calendar of the 1966 Gregorian calendar. 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. Events 1740 - Maria Theresa takes the throne of Austria. France, Prussia, Bavaria and Saxony Year 1967 ( MCMLXVII) was a Common year starting on Sunday (link will display full calendar of the 1967 Gregorian calendar. 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. Events 1740 - Maria Theresa takes the throne of Austria. France, Prussia, Bavaria and Saxony Year 1967 ( MCMLXVII) was a Common year starting on Sunday (link will display full calendar of the 1967 Gregorian calendar. 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. Events 1009 - The Church of the Holy Sepulchre, a Christian church in Jerusalem, is completely destroyed by the Fatimid Year 1968 ( MCMLXVIII) was a Leap year starting on Monday (link will display full calendar of the Gregorian calendar. 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. Events 539 BC - King Cyrus The Great of Persia marches into the city of Babylon, releasing the Jews from almost Year 1969 ( MCMLXIX) was a Common year starting on Wednesday (link will display full calendar of the Gregorian calendar. 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. Events 456 - Magister militum Ricimer defeats the Emperor Avitus at Piacenza and becomes master of the western Year 1974 ( MCMLXXIV) was a Common year starting on Tuesday (link will display full calendar of the 1974 Gregorian calendar. IEEE.

S. A. Greibach.

Formal languages: Origins and directions.

In 20th Annual Symposium on Foundations of Computer Science, pages 66-90, San Juan, Puerto Rico, 29-31 October 1979. Events 445 BC – Ezra reads the Book of the Law to the Israelites in Jerusalem (see Nehemiah 91 NLTse Year 1979 ( MCMLXXIX) was a Common year starting on Monday (link displays the 1979 Gregorian calendar) 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. Year 1971 ( MCMLXXI) was a Common year starting on Friday (link will display full calendar of the 1971 Gregorian calendar. IEEE.

Contents

Work and Contributions

From ACM Digital Library:

From FOCS Bibliography

Others

See also