stringtranslate.com

Sheila Greibach

Sheila Adele Greibach (nacida el 6 de octubre de 1939 en la ciudad de Nueva York) es una investigadora estadounidense en lenguajes formales en computación, autómatas , teoría de compiladores y ciencias de la computación . Es profesora emérita de Ciencias de la Computación en la Universidad de California en Los Ángeles y su trabajo más destacado 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 las gramáticas W , los autómatas pushdown y los problemas de decidibilidad .

Carrera temprana

Greibach obtuvo una licenciatura ( summa cum laude ) en Lingüística y Matemáticas Aplicadas en el Radcliffe College en 1960, y dos años después obtuvo una licenciatura en Matemáticas Aplicadas. En 1963, obtuvo un doctorado en la Universidad de Harvard , bajo la dirección de Anthony Oettinger [1] con una tesis doctoral titulada "Inversos de generadores de estructura sintagmática".

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

Trabajo y contribuciones

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 procede de la Biblioteca Digital ACM y el resto de la Bibliografía FOCS de David M. Jones.

De la Biblioteca Digital ACM

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

Todo lenguaje determinista libre de contexto puede ser aceptado por un pda determinista de retardo finito con saltos. Al aumentar el número de tipos u ocurrencias de saltos, aumenta la familia de lenguajes aceptados con retardo finito. Por lo tanto, la familia de lenguaje determinista libre de contexto es un AFDL principal; existe un lenguaje libre de contexto tal que todo lenguaje libre de contexto es una imagen gsm inversa de o .

"Algunas restricciones a las gramáticas W" Actas del sexto simposio anual de la ACM sobre teoría de la computación, abril de 1974

Se explora el efecto de algunas restricciones en las gramáticas W (la formalización de la sintaxis de ALGOL 68 ). Dos familias incomparables examinadas en profundidad son WRB (lenguajes generados por gramáticas W normales basadas en reglas) y WS (lenguajes generados por gramáticas W simples). Ambos contienen adecuadamente los lenguajes libres de contexto y están adecuadamente contenidos en la familia de lenguajes de tiempo cuasireal. Además, WRB está cerrado bajo iteraciones anidadas...

"Una jerarquía infinita de lenguajes libres de contexto", Journal of the ACM , volumen 16, número 1, enero de 1969

"Un nuevo teorema de forma normal para gramáticas de estructura de frase independientes del contexto", JACM , volumen 12, número 1, enero de 1965

"La insolubilidad del reconocimiento de lenguajes lineales e independientes del contexto", JACM , volumen 13, número 4, octubre de 1966

Se demuestra que el problema de si un lenguaje dado libre de contexto es lineal es recursivamente indecidible.

Trabajos en coautoría

"Multitape AFA", 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 EP Friedman, " JACM ", octubre de 1980, volumen 27, número 4

"Autómatas de pila y compilación", coescrito con Seymour Ginsburg y Michael A. Harrison, " JACM ", enero de 1967, volumen 14, número 1

La compilación consta de dos partes: reconocimiento y traducción. Se presenta un modelo matemático que incorpora características destacadas de muchas técnicas de compilación modernas. El modelo, llamado autómata de pila, tiene la característica deseable de ser de naturaleza determinista. Este dispositivo determinista se generaliza a un dispositivo no determinista (autómata de pila no determinista) y se indican instancias particulares de este dispositivo más general. Los conjuntos aceptados por los autómatas de pila no deterministas son recursivos ...

"Lenguajes en tiempo cuasi-real (resumen ampliado)", coescrito con Ronald V. Book, Actas del primer simposio anual de la ACM sobre teoría de la computación, mayo de 1969

Los lenguajes de tiempo cuasi-real son los lenguajes aceptados por las máquinas de Turing multicinta no deterministas en tiempo real. La familia de lenguajes de tiempo cuasi-real forma una familia abstracta de lenguajes cerrados bajo intersección, borrado lineal e inversión. Es idéntica a la familia de lenguajes aceptados por las máquinas de Turing multicinta no deterministas en tiempo lineal. Cada lenguaje de tiempo cuasi-real puede ser aceptado en tiempo real por una máquina no determinista de una pila, un almacenamiento en pila, y puede ser aceptado por una máquina de almacenamiento en pila.

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

Se presentan varias operaciones que preservan los conjuntos aceptados por autómatas de pila unidireccional o los conjuntos aceptados por autómatas de pila unidireccional deterministas. Por ejemplo, la transducción secuencial preserva los primeros; la complementación de conjuntos, los segundos. También se consideran varias cuestiones de resolubilidad.

"Aceptores de Turing y AFL limitados en tiempo y en cinta (resumen ampliado)", coautor con Ronald V. Book y Ben Wegbreit, Actas del segundo simposio anual de la ACM sobre teoría de la computación, mayo de 1970

Se estudian las clases de complejidad de los lenguajes formales definidos por aceptores de Turing limitados en el tiempo y en la cinta, con el objetivo de mostrar condiciones suficientes para que estas clases sean AFL y AFL principales.

"AFL borrable de manera uniforme", coescrito con Seymour Ginsburg y Jonathan Goldstine, Actas del cuarto simposio anual de la ACM sobre teoría de la computación, mayo de 1972

Este artículo demostró que varias familias conocidas tienen la propiedad (*). En particular, los autores demostraron que la familia de lenguajes libres de contexto efectivamente tiene esta propiedad. Además, demostramos que varias subfamilias conocidas de los lenguajes libres de contexto, como los lenguajes de un solo contador, tienen la propiedad (*). Finalmente, demostramos que hay familias que satisfacen (*) que no son subfamilias de los lenguajes libres de contexto, ya que demostramos que cualquier familia generada a partir de lenguajes de un solo contador... [ aclaración necesaria ]
Sistemas de análisis formal
Sheila A. Greibach
Agosto de 1964
Comunicaciones de la ACM, Volumen 7, Número 8
El análisis sintáctico automático ha adquirido importancia recientemente tanto para el procesamiento de datos en lenguaje natural como para los compiladores orientados a la sintaxis . Un sistema de análisis sintáctico formal G = (V, μ, T, R) consta de dos vocabularios finitos disjuntos, V y T, una función de muchos a muchos, μ, de V a T, y un conjunto recursivo R de cadenas en T llamadas clases de oraciones sintácticas...

De la bibliografía de FOCS

Seymour Ginsburg y Sheila Greibach.
Lenguajes libres de contexto deterministas.
En Actas del Sexto Simposio Anual sobre Teoría de Circuitos de Conmutación y Diseño Lógico , páginas 203-220. IEEE, 1965.
Seymour Ginsburg, Sheila A. Greibach y Michael A. Harrison.
Autómatas de pila unidireccional (resumen extendido).
En Conference Record of 1966 Seventh Annual Symposium on Switching and Autómata Theory , páginas 47-52, Berkeley, California, 26-28 de octubre de 1966. IEEE.
Sheila A. Greibach.
Una jerarquía infinita de lenguajes libres de contexto.
En Conference Record of 1967 Eighth Annual Symposium on Switching and Autómata Theory, páginas 32-36, Austin, Texas, 18-20 de octubre de 1967. IEEE.
Seymour Ginsburg y Sheila Greibach.
Familias abstractas de lenguas.
En Conference Record of 1967 Eighth Annual Symposium on Switching and Autómata Theory, páginas 128-139, Austin, Texas, 18-20 de octubre de 1967. IEEE. Citas.
Sheila Greibach.
Comprobación de autómatas y lenguajes de pila unidireccional (resumen extendido).
En Conference Record of 1968 Ninth Annual Symposium on Switching and Autómata Theory, páginas 287-291, Schenectady, Nueva York, 15-18 de octubre de 1968. IEEE. Citas.
Sheila A. Greibach.
AFL completos y sustitución iterada anidada.
En Conference Record of 1969 Décimo Simposio Anual sobre Conmutación y Teoría de Autómatas, páginas 222-230, Waterloo, Ontario, Canadá, 15-17 de octubre de 1969. IEEE.
JW Carlyle, SA Greibach y A. Paz.
Un sistema generador bidimensional que modela el crecimiento por división celular binaria (informe preliminar).
En el 15º Simposio Anual sobre Conmutación y Teoría de Autómatas, páginas 1-12, Universidad de Nueva Orleans, 14-16 de octubre de 1974. IEEE.
Sociedad Anónima Greibach.
Lenguajes formales: orígenes y direcciones.
En 20º Simposio Anual sobre Fundamentos de la Ciencia de la Computación , páginas 66-90, San Juan, Puerto Rico, 29–31 de octubre de 1979. IEEE.

Otros

Ronald Book, Shimon Even, Sheila Greibach y Gene Ott.
Ambigüedad en gráficos y expresiones.
IEEE Transactions on Computers, vol. c-20, No. 2, febrero de 1971. IEEE.

Véase también

Referencias

  1. ^ Sheila Greibach en el Proyecto de Genealogía Matemática

Enlaces externos