Sheila Greibach - Sheila Greibach

Sheila Greibach
Geboren ( 1939-10-06 )6. Oktober 1939 (80 Jahre)
Alma Mater Radcliffe College
Harvard University
Bekannt für Greibach-Normalform , Greibachs Satz
Wissenschaftliche Karriere
Felder Theoretische Informatik
Formale Sprache in Computing
Automaten
Computational Complexity
Compiler Theory
Institutionen Universität von Kalifornien, Los Angeles
Harvard University
Doktorvater Anthony Oettinger
Doktoranden Ronald V. Buch , Michael J. Fischer , Jean Gallier

Sheila Adele Greibach (* 6. Oktober 1939 in New York City) ist Forscherin in formalen Sprachen in den Bereichen Computer, Automaten , Compilertheorie und Informatik . Sie ist emeritierte Professorin für Informatik an der University of California in Los Angeles . Zu ihren bemerkenswerten Arbeiten gehört die Zusammenarbeit mit Seymour Ginsburg und Michael A. Harrison bei der kontextsensitiven Analyse mithilfe des Stapelautomatenmodells .

Neben der Festlegung der Normalform ( Greibach-Normalform ) für kontextfreie Grammatiken untersuchte sie 1965 auch Eigenschaften von W-Grammatiken , Pushdown-Automaten und Entscheidbarkeitsprobleme .

Frühe Karriere

Greibach erwarb 1960 einen AB-Abschluss ( summa cum laude ) in Linguistik und Angewandter Mathematik am Radcliffe College und zwei Jahre später einen AM-Abschluss. 1963 promovierte sie an der Harvard University , beraten von Anthony Oettinger mit einer Doktorarbeit mit dem Titel "Inverses of Phrase Structure Generators".

Sie arbeitete weiterhin in Harvard an der Abteilung für Ingenieurwissenschaften und Angewandte Physik, bis sie 1969 an die UCLA wechselte , wo sie bis heute Professorin war (Stand März 2014).

Arbeit und Beiträge

Zu ihren Schülern gehörten Ronald V. Book und Michael J. Fischer . Die folgende Liste zeigt einige ihrer Arbeiten. Der obere Teil der Liste stammt aus der ACM Digital Library und der Rest aus der FOCS Bibliography von David M. Jones.

Aus der ACM Digital Library

"Jump PDAs, deterministische kontextfreie Sprachen, Haupt-AFDLs und polynomielle Zeiterkennung (Extended Abstract)", Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 1973

Jede deterministische kontextfreie Sprache kann von einer deterministischen endlichen Verzögerung pda mit Sprüngen akzeptiert werden . Durch Erhöhen der Anzahl der Arten oder des Auftretens von Sprüngen wird die Sprachfamilie erhöht, die mit endlicher Verzögerung akzeptiert wird. Daher ist die Familie der deterministischen kontextfreien Sprache eine Haupt-AFDL; Es gibt eine kontextfreie Sprache, so dass jede kontextfreie Sprache ein inverses GSM- Bild von oder ist .

"Einige Einschränkungen der W-Grammatik" Vorträge des sechsten jährlichen ACM-Symposiums zur Theorie des Rechnens, April 1974

Die Auswirkungen einiger Einschränkungen auf W-Grammatiken (die Formalisierung der Syntax von ALGOL 68 ) werden untersucht. Zwei unvergleichliche Familien, die ausführlich untersucht wurden, sind WRB (Sprachen, die durch normale reguläre W-Grammatiken erzeugt werden) und WS (Sprachen, die durch einfache W-Grammatiken erzeugt werden). Beide enthalten ordnungsgemäß die kontextfreien Sprachen und sind ordnungsgemäß in der Familie der Quasirealtime-Sprachen enthalten. Darüber hinaus wird WRB unter verschachtelter Iteration geschlossen ...

"Eine unendliche Hierarchie kontextfreier Sprachen", Journal of the ACM , Band 16, Ausgabe 1, Januar 1969

"Ein neuer Normalformsatz für kontextfreie Phrasenstrukturgrammatiken", JACM , Band 12, Ausgabe 1, Januar 1965

"Die Unlösbarkeit der Erkennung linearer kontextfreier Sprachen", JACM , Band 13, Ausgabe 4, Oktober 1966

Das Problem, ob eine bestimmte kontextfreie Sprache linear ist, ist rekursiv unentscheidbar.

Mitverfasste Werke

"Multitape AFA", gemeinsam mit Seymour Ginsburg, Journal of the ACM , Band 19, Ausgabe 2, April 1972, verfasst

"Superdeterministic PDAs: A Subcase with a Decidable Inclusion Problem", gemeinsam mit EP Friedman, " JACM ", Oktober 1980, Band 27, Ausgabe 4

"Stack Automata and Compiling", gemeinsam mit Seymour Ginsburg und Michael A. Harrison verfasst, " JACM ", Januar 1967, Band 14, Ausgabe 1

Die Zusammenstellung besteht aus zwei Teilen: Anerkennung und Übersetzung. Es wird ein mathematisches Modell vorgestellt, das die wichtigsten Merkmale vieler moderner Kompiliertechniken verkörpert. Das Modell, das als Stapelautomat bezeichnet wird, hat das wünschenswerte Merkmal, deterministischer Natur zu sein. Diese deterministische Vorrichtung wird auf eine nichtdeterministische Vorrichtung (nichtdeterministischer Stapelautomat) verallgemeinert, und bestimmte Fälle dieser allgemeineren Vorrichtung werden notiert. Von nichtdeterministischen Stapelautomaten akzeptierte Mengen sind rekursiv ...

"Quasi-Echtzeitsprachen (Extended Abstract)", gemeinsam mit Ronald V. Book verfasst, Proceedings of the first annual ACM symposium on Theory of Computing, Mai 1969

Quasi-Echtzeitsprachen sind die Sprachen, die von nichtdeterministischen Multitape- Turing-Maschinen in Echtzeit akzeptiert werden . Die Familie der Quasi-Echtzeit-Sprachen bildet eine abstrakte Familie von Sprachen, die unter Schnittmenge, linearem Löschen und Umkehren geschlossen sind. Es ist identisch mit der Sprachfamilie, die von nichtdeterministischen Multitape-Turing-Maschinen in linearer Zeit akzeptiert wird. Jede Quasi-Echtzeitsprache kann in Echtzeit von einem nicht deterministischen Stapel, einer Pushdown-Speichermaschine und ...

"One-Way-Stack-Automaten", gemeinsam mit Seymour Ginsburg und Michael A. Harrison verfasst, " JACM ", April 1967, Band 14, Ausgabe 2

Es wird eine Reihe von Operationen vorgestellt, die entweder Sätze beibehalten, die von Einweg-Stapelautomaten akzeptiert werden, oder Sätze beibehalten, die von deterministischen Einweg-Stapelautomaten akzeptiert werden. Beispielsweise bewahrt die sequentielle Transduktion die erstere; Set Komplementation, letztere. Es werden auch mehrere Fragen zur Lösbarkeit berücksichtigt.

"Tape- und zeitgebundene Turing-Akzeptoren und AFLs (Extended Abstract)", zusammen mit Ronald V. Book und Ben Wegbreit, Proceedings des zweiten jährlichen ACM-Symposiums zur Theorie des Rechnens, Mai 1970

Komplexitätsklassen formaler Sprachen, die durch zeit- und bandgebundene Turing-Akzeptoren definiert sind, werden mit dem Ziel untersucht, ausreichende Bedingungen dafür aufzuzeigen, dass diese Klassen AFLs und Haupt-AFLs sind.

"Uniformly erasable AFL", gemeinsam mit Seymour Ginsburg und Jonathan Goldstine verfasst, Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, Mai 1972

Dieses Papier zeigte, dass eine Reihe bekannter Familien Eigentum haben (*). Insbesondere haben die Autoren bewiesen, dass die Familie der kontextfreien Sprachen tatsächlich diese Eigenschaft besitzt. Darüber hinaus zeigen wir, dass mehrere bekannte Unterfamilien der kontextfreien Sprachen, wie z. B. die Einzählersprachen , die Eigenschaft (*) haben. Schließlich zeigen wir, dass es Familien gibt, die (*) erfüllen und keine Unterfamilien der kontextfreien Sprachen sind, denn wir beweisen, dass jede Familie aus ...
Formale Parsing-Systeme
Sheila A. Greibach
August 1964
Mitteilungen des ACM, Band 7, Ausgabe 8
Die automatische syntaktische Analyse ist in letzter Zeit sowohl für die Verarbeitung natürlicher Daten als auch für syntaxgesteuerte Compiler wichtig geworden . Ein formales Parsing-System G = (V, μ, T, R) besteht aus zwei endlichen disjunkten Vokabularen V und T, einer Viel-Viel-Abbildung μ von V auf T und einer rekursiven Menge R von Strings in T, die als syntaktisch bezeichnet wird Satzklassen ...

Aus der FOCS-Bibliographie

Seymour Ginsburg und Sheila Greibach.
Deterministische kontextfreie Sprachen.
In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design , S. 203-220. IEEE, 1965.
Seymour Ginsburg, Sheila A. Greibach und Michael A. Harrison.
Einweg-Stapelautomaten (erweiterte Zusammenfassung).
In Conference Record of Seventh Annual Symposium on Switching and Automata Theory von 1966 , S. 47-52, Berkeley, Kalifornien, 26.-28. Oktober 1966. IEEE.
Sheila A. Greibach.
Eine unendliche Hierarchie kontextfreier Sprachen.
Im Konferenzbericht des achten jährlichen Symposiums von 1967 über Switching und Automatentheorie, Seiten 32-36, Austin, Texas, 18.-20. Oktober 1967. IEEE.
Seymour Ginsburg und Sheila Greibach.
Abstrakte Sprachfamilien.
Im Konferenzbericht des achten jährlichen Symposiums von 1967 über Switching und Automatentheorie, Seiten 128-139, Austin, Texas, 18.-20. Oktober 1967. IEEE. Zitate.
Sheila Greibach.
Überprüfen von Automaten und Einweg-Stack-Sprachen (erweiterte Zusammenfassung).
In Conference Record of 1968, 9. jährliches Symposium über Switching und Automatentheorie, Seiten 287-291, Schenectady, New York, 15.-18. Oktober 1968. IEEE. Zitate.
Sheila A. Greibach.
Vollständige AFLs und verschachtelte iterierte Substitution.
Im Konferenzbericht des zehnten jährlichen Symposiums über Switching und Automatentheorie von 1969, Seiten 222-230, Waterloo, Ontario, Kanada, 15.-17. Oktober 1969. IEEE.
JW Carlyle, SA Greibach und A. Paz.
Ein zweidimensionales Erzeugungssystem, das das Wachstum durch binäre Zellteilung modelliert (vorläufiger Bericht).
Im 15. jährlichen Symposium über Switching und Automatentheorie, Seiten 1-12, The University of New Orleans, 14.-16. Oktober 1974. IEEE.
SA Greibach.
Formale Sprachen: Ursprünge und Richtungen.
Im 20. jährlichen Symposium über Grundlagen der Informatik , Seiten 66-90, San Juan, Puerto Rico, 29.-31. Oktober 1979. IEEE.

Andere

Ronald Book, Shimon Even, Sheila Greibach und Gene Ott.
Mehrdeutigkeit in Grafiken und Ausdrücken.
IEEE Transactions on Computers, vol. c-20, Nr. 2, Februar 1971. IEEE.

Siehe auch

Verweise

Externe Links