Sheila Greibach

Sheila Adele Greibach (nacida el 6 de octubre de 1939 en la ciudad de Nueva York) es una investigadora de lenguajes formales en informática, autómatas, teoría de compiladores e informática. Es profesora emérita de Ciencias de la Computación en la Universidad de California, Los Ángeles, y su trabajo notable incluye trabajar con Seymour Ginsburg y Michael A. Harrison en análisis sensible al contexto utilizando el modelo de autómata de pila.

Además de establecer la forma normal (forma normal de Greibach) para gramáticas libres de contexto, en 1965 también investigó las propiedades de gramáticas W, autómatas pushdown y problemas de decidibilidad.

Carrera temprana

Greibach obtuvo un título A.B. Licenciatura (summa cum laude) en Lingüística y Matemáticas Aplicadas de Radcliffe College en 1960, y dos años después obtuvo un A.M. grado. En 1963, obtuvo un doctorado en la Universidad de Harvard, asesorada por Anthony Oettinger, con una tesis doctoral titulada "Inverses of Phrase Structure Generators".

Continuó trabajando en Harvard en la División de Ingeniería y Física Aplicada hasta 1969 cuando se mudó a UCLA, donde ha sido profesora hasta la actualidad (a marzo de 2014).

Trabajo y aportaciones

Entre sus alumnos se encontraban Ronald V. Book y Michael J. Fischer. La siguiente lista indica algunos de sus trabajos. La parte superior de la lista proviene de la Biblioteca Digital ACM y el resto de la Bibliografía FOCS de David M. Jones.

De la biblioteca digital ACM

"PDA Jump, lenguajes deterministas libres de contexto, AFDL principales y reconocimiento de tiempo polinomial (Resumen ampliado)," Actas del quinto simposio anual de la ACM sobre teoría de la computación, abril de 1973

Cada lenguaje determinista sin contexto puede ser aceptado por un retraso finito determinista pda con saltos. Aumentar el número de tipos o ocurrencias de saltos aumenta la familia de idiomas aceptados con retraso finito. Por lo tanto, la familia del lenguaje determinista sin contexto es un AFDL principal; hay un lenguaje sin contexto ${displaystyle L_{0}$ tal que cada lenguaje sin contexto es una imagen inversa de gsm ${displaystyle L_{0}$ o ${displaystyle L_{0}-{e}$.

"Algunas restricciones en las gramáticas W" Actas del sexto simposio anual de la ACM sobre teoría de la informática, abril de 1974

Se explora el efecto de algunas restricciones a las W-grammars (la formalización de la sintaxis de ALGOL 68). Dos familias incomparables examinadas a lo largo son WRB (languages generados por W-grammars normalizados) y WS (languages generados por simples W-grammars). Ambos contienen adecuadamente los idiomas sin contexto y están debidamente contenidos en la familia de idiomas cuasi reales. Además, el WRB está cerrado bajo el itinerario anidado...

"Una jerarquía infinita de lenguajes libres de contexto," Revista de la ACM, Volumen 16 Número 1, enero de 1969

"Un nuevo teorema de forma normal para gramáticas de estructuras de frases libres de contexto," JACM, Volumen 12 Número 1, enero de 1965

"La insolubilidad del reconocimiento de lenguajes lineales libres de contexto," JACM, Volumen 13 Número 4, octubre de 1966

El problema de si un idioma libre de contexto determinado es lineal se demuestra que es recursivamente indecible.

Obras en coautoría

"AFA multicinta," en coautoría con Seymour Ginsburg, Journal of the ACM, volumen 19, número 2, abril de 1972

"PDA superdeterministas: un subcaso con un problema de inclusión decidible", en coautoría con E. P. Friedman, "JACM", octubre de 1980, volumen 27, número 4

"Apilar autómatas y compilar," en coautoría con Seymour Ginsburg y Michael A. Harrison, "JACM", enero de 1967, volumen 14, número 1

Recopilación consta de dos partes, reconocimiento y traducción. Se presenta un modelo matemático que encarna características salientes de muchas técnicas modernas de compilación. El modelo, llamado autómata de pila, tiene la característica deseable de ser determinista en la naturaleza. Este dispositivo determinista se generaliza a un dispositivo no determinista (automatono de pila no determinista) y se señalan casos particulares de este dispositivo más general. Los conjuntos aceptados por la pila nodeterminista automata son recursi...

"Lenguajes casi en tiempo real (resumen extendido)," en coautoría con Ronald V. Book, Actas del primer simposio anual de ACM sobre Teoría de la Computación, mayo de 1969

Los idiomas cuasi-real son los idiomas aceptados por las máquinas multitape no deterministas Turing en tiempo real. La familia de lenguas cuasi-realistas forma una familia abstracta de idiomas cerrados bajo intersección, borrado lineal y reversión. Es idéntica a la familia de idiomas aceptada por máquinas multitape no deterministas en tiempo lineal. Cada lenguaje cuasi-realtime puede ser aceptado en tiempo real por una pila no-determinista, una máquina de la tienda de empuje, y puede ser...

"Autómatas de pila unidireccional" en coautoría con Seymour Ginsburg y Michael A. Harrison, "JACM", abril de 1967, volumen 14, número 2

Se presentan una serie de operaciones que conservan conjuntos aceptados por automata de pila de una sola vía o conjuntos de conservación aceptados por automata de una sola vía determinista. Por ejemplo, la transducción secuencial preserva al primero; establece la complementación, este último. También se examinan varias preguntas sobre la soledad.

"Aceptadores de Turing y AFL con límite de tiempo y cinta (resumen extendido)" en coautoría con Ronald V. Book y Ben Wegbreit, Actas del segundo simposio anual de ACM sobre teoría de la informática, mayo de 1970

Se estudian clases de complejidad de idiomas formales definidos por los aceptadores de Turing con tiempo y cinta, con el objetivo de mostrar condiciones suficientes para que estas clases sean AFL y sean principales AFLs.

"AFL uniformemente borrable", en coautoría con Seymour Ginsburg y Jonathan Goldstine, Actas del cuarto simposio anual de ACM sobre teoría de la informática, mayo de 1972

Este documento demostró que varias familias conocidas tienen propiedades (*). En particular, los autores demostraron que la familia de lenguas libres de contexto tiene este bien. Además, mostramos que varias subfamilias familiares de los idiomas sin contexto, como los idiomas de un solo usuario, tienen propiedades (*). Finalmente, mostramos que hay familias satisfactorias (*) que no son subfamilias de los lenguajes sin contexto, porque demostramos que cualquier familia generada a partir de...

Sistemas de pareado térmico

Sheila A. Greibach

Agosto de 1964

Comunicaciones de la ACM, Volumen 7 Edición 8

El análisis sintáctico automático se ha convertido recientemente en importante tanto para el procesamiento de datos de lenguaje natural como para los compiladores dirigidos por sintaxis. Un sistema formal de persing G = (V, μ, T, R) consiste en dos vocabularios descomunales finitos, V y T, un mapa de muchas personas, μ, de V a T, y un conjunto recursivo R de cadenas en T llamadas clases de frases sintácticas...

De la bibliografía de FOCS

Seymour Ginsburg y Sheila Greibach.

Lenguas libres de contexto definitorio.

En Proceedings of the sixth Annual Symposium on Switching Circuit Theory and Logical Design, págs. 203 a 220. IEEE, 1965.

Seymour Ginsburg, Sheila A. Greibach, y Michael A. Harrison.

Automata de pila de una sola vía (abstracto previsto).

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.

Una jerarquía infinita de lenguajes sin contexto.

En el Registro de Conferencias de 1967 Octavo Simposio Anual sobre Interrupción y Teoría Automata, págs. 32 a 36, Austin, Texas, 18 a 20 de octubre de 1967. IEEE.

Seymour Ginsburg y 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. Citaciones.

Sheila Greibach.

Comprobación de autómatas y idiomas de pila de una sola vía (abstracto previsto).

In Conference Record of 1968 Noveth Annual Symposium on Switching and Automata Theory, pages 287-291, Schenectady, New York, 15–18 October 1968. IEEE. Citaciones.

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 y A. Paz.

Un crecimiento del sistema generador bidimensional por división celular binaria (informe preliminar).

En 15o Simposio Anual sobre Interrupción y Teoría Automata, págs. 1 a 12, Universidad de Nueva Orleans, 14 a 16 de octubre de 1974. IEEE.

S. A. Greibach.

Lenguas formales: Orígenes y direcciones.

En el 20o Simposio Anual sobre Fundaciones de Ciencias de la Computación, págs. 66 a 90, San Juan, Puerto Rico, 29 a 31 de octubre de 1979. IEEE.

Otros

Ronald Book, Shimon Even, Sheila Greibach y Gene Ott.

Ambigüedad en Gráficos y Expresiones.

Transacciones IEEE en Computadoras, vol. c-20, No. 2, febrero 1971. IEEE.