Sheila Greibach - Sheila Greibach
Sheila Greibach | |
---|---|
Geboren |
|
6. Oktober 1939
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.