Шейла Грейбах
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Шейла Грейбах | |
|---|---|
| Рожденный | 6 октября 1939 г. |
| Альма-матер | Рэдклифф Колледж Гарвардский университет |
| Известный | Нормальная форма Грейбаха , теорема Грейбаха |
| Научная карьера | |
| Поля | Теоретическая информатика Формальный язык в вычислительной технике Автоматы Вычислительная сложность Теория компилятора |
| Учреждения | Калифорнийский университет, Лос-Анджелес Гарвардский университет |
| Докторантура | Энтони Эттингер |
| Докторанты | Рональд В. Бук , Майкл Дж. Фишер , Жан Галье |
Шейла Адель Грейбах (родилась 6 октября 1939 года в Нью-Йорке) — американский исследователь формальных языков в области вычислений, автоматов , теории компиляторов и информатики . Она является почетным профессором компьютерных наук , Калифорнийского университета в Лос-Анджелесе и ее известная работа включает работу с Сеймуром Гинзбургом и Майклом А. Харрисоном в области контекстно-зависимого анализа с использованием модели стекового автомата .
Помимо установления нормальной формы ( нормальной формы Грейбаха ) для контекстно-свободных грамматик , в 1965 году она также исследовала свойства , W-грамматик автоматов с выталкиванием и проблем разрешимости .
Ранняя карьера
[ редактировать ]Грейбах получил степень AB ( с отличием ) в области лингвистики и прикладной математики в Рэдклифф-колледже в 1960 году, а через два года после этого получил степень AM. В 1963 году ей была присвоена степень доктора философии в Гарвардском университете по рекомендации Энтони Эттингера. [1] защитил кандидатскую диссертацию на тему «Инверсии генераторов фразовой структуры».
Она продолжала работать в Гарварде на факультете инженерии и прикладной физики до 1969 года, когда она переехала в Калифорнийский университет в Лос-Анджелесе , где она является профессором до настоящего времени (по состоянию на март 2014 года).
Работа и вклад
[ редактировать ]Среди ее учеников были Рональд В. Бук и Майкл Дж. Фишер .В следующем списке указаны некоторые из ее работ. Верхняя часть списка взята из цифровой библиотеки ACM , а остальная часть — из библиографии FOCS Дэвида М. Джонса.
Из цифровой библиотеки ACM
[ редактировать ]«Jump PDA, детерминированные контекстно-свободные языки, основные AFDL и полиномиальное распознавание времени (расширенное резюме)», Материалы пятого ежегодного симпозиума ACM по теории вычислений, апрель 1973 г.
- Любой детерминированный контекстно-свободный язык может быть принят детерминированным КПК с конечной задержкой и переходами. Увеличение количества типов или случаев перехода увеличивает семейство языков, принимаемых с конечной задержкой. Следовательно, семейство детерминированных контекстно-свободных языков является основным AFDL; есть контекстно-свободный язык так что каждый контекстно-свободный язык является обратным GSM- образом или .
«Некоторые ограничения на W-грамматики»Материалы шестого ежегодного симпозиума ACM по теории вычислений, апрель 1974 г.
- влияние некоторых ограничений на W-грамматики (формализация синтаксиса АЛГОЛА 68 Исследуется ). Подробно рассмотрены два несравнимых семейства: WRB (языки, порожденные обычными W-грамматиками) и WS (языки, порожденные простыми W-грамматиками). Оба должным образом содержат контекстно-свободные языки и принадлежат к семейству языков квазиреального времени. Кроме того, WRB закрыт при вложенной итерации...
«Бесконечная иерархия контекстно-свободных языков», журнал ACM , том 16, выпуск 1, январь 1969 г.
«Новая теорема о нормальной форме для грамматик контекстно-свободной фразовой структуры», JACM , том 12, выпуск 1, январь 1965 г.
«Неразрешимость распознавания линейных контекстно-свободных языков», JACM , том 13, выпуск 4, октябрь 1966 г.
- Показано, что проблема того, является ли данный контекстно-свободный язык линейным, рекурсивно неразрешима.
Соавторские работы
[ редактировать ]«Многокассетный AFA», в соавторстве с Сеймуром Гинзбургом, Журнал ACM , том 19, выпуск 2, апрель 1972 г.
«Супердетерминированные КПК: подслучай с разрешимой проблемой включения», в соавторстве с Э. П. Фридманом, « JACM », октябрь 1980 г., том 27, выпуск 4.
«Стековые автоматы и компиляция», в соавторстве с Сеймуром Гинзбургом и Майклом А. Харрисоном, « JACM », январь 1967 г., том 14, выпуск 1.
- Компиляция состоит из двух частей: распознавания и перевода. Представлена математическая модель, воплощающая в себе основные черты многих современных методов составления данных. Модель, называемая стековым автоматом, имеет то преимущество, что она детерминирована по своей природе. Это детерминированное устройство обобщается до недетерминированного устройства (недетерминированного стекового автомата) и отмечаются частные случаи этого более общего устройства. Множества, принимаемые недетерминированными стековыми автоматами, являются рекурсивными.
«Языки квазиреального времени (расширенное резюме)», в соавторстве с Рональдом В. Буком, Труды первого ежегодного симпозиума ACM по теории вычислений, май 1969 г.
- Языки квазиреального времени — это языки, которые принимаются недетерминированными многоленточными машинами Тьюринга в реальном времени. Семейство языков квазиреального времени образует абстрактное семейство языков, замкнутое относительно пересечения, линейного стирания и обращения. Он идентичен семейству языков, принимаемых недетерминированными многоленточными машинами Тьюринга в линейном времени. Каждый язык квази-реального времени может быть принят в реальном времени недетерминированной машиной с одним стеком и одним магазином с выпадающим меню и может быть...
«Автоматы с односторонним стеком», в соавторстве с Сеймуром Гинзбургом и Майклом А. Харрисоном, « JACM », апрель 1967 г., том 14, выпуск 2.
- Представлен ряд операций, которые либо сохраняют множества, принимаемые односторонними стек-автоматами, либо сохраняют множества, принимаемые детерминированными односторонними стек-автоматами. Например, последовательная трансдукция сохраняет первую; установить дополнение, последнее. Рассмотрены также некоторые вопросы разрешимости.
«Акцепторы Тьюринга и AFL, ограниченные по времени и ленте (расширенное резюме)»в соавторстве с Рональдом В. Буком и Беном Вегбрейтом, Труды второго ежегодного симпозиума ACM по теории вычислений, май 1970 г.
- Классы сложности формальных языков, определяемые акцепторами Тьюринга, ограниченными по времени и ленте, изучаются с целью показать достаточные условия для того, чтобы эти классы были AFL и были главными AFL.
«Равномерно стираемый AFL», в соавторстве с Сеймуром Гинзбургом и Джонатаном Голдстайном, Труды четвертого ежегодного симпозиума ACM по теории вычислений, май 1972 г.
- В данной статье показано, что ряд известных семейств обладают свойством (*). В частности, авторы доказали, что семейство контекстно-свободных языков действительно обладает этим свойством. Кроме того, мы показываем, что несколько знакомых подсемейств контекстно-свободных языков, таких как языки с одним счетчиком , обладают свойством (*). Наконец, мы показываем, что существуют семейства, удовлетворяющие (*), которые не являются подсемействами контекстно-свободных языков, поскольку мы доказываем, что любое семейство, порожденное однолет... [ нужны разъяснения ]
- Формальные системы синтаксического анализа
- Шейла А. Грейбах
- август 1964 г.
- Сообщения ACM, том 7, выпуск 8
- Автоматический синтаксический анализ в последнее время стал важным как для естественного языка обработки данных , так и для компиляторов, управляемых синтаксисом . Формальная система синтаксического анализа G = (V, µ, T, R) состоит из двух конечных непересекающихся словарей, V и T, отображения типа «многие-многие» µ из V в T и рекурсивного набора R строк в T, называемого синтаксическим. классы предложений...
Из библиографии FOCS
[ редактировать ]- Сеймур Гинзбург и Шейла Грейбах.
- Детерминированные контекстно-свободные языки.
- В материалах шестого ежегодного симпозиума по теории коммутационных цепей и логическому проектированию , страницы 203–220. ИИЭР, 1965.
- Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон.
- Автоматы с односторонним стеком (расширенная абстракция).
- В протоколе конференции седьмого ежегодного симпозиума 1966 года по теории коммутации и автоматов , страницы 47–52, Беркли, Калифорния, 26–28 октября 1966 года. IEEE.
- Шейла А. Грейбах.
- Бесконечная иерархия контекстно-свободных языков.
- В протоколе конференции восьмого ежегодного симпозиума 1967 года по теории коммутации и автоматов, страницы 32–36, Остин, Техас, 18–20 октября 1967 года. IEEE.
- Сеймур Гинзбург и Шейла Грейбах.
- Абстрактные семьи языков.
- В протоколе конференции восьмого ежегодного симпозиума 1967 года по теории коммутации и автоматов, страницы 128–139, Остин, Техас, 18–20 октября 1967 года. IEEE. Цитаты.
- Шейла Грейбах.
- Проверка автоматов и языков с односторонним стеком (расширенная аннотация).
- В протоколе конференции девятого ежегодного симпозиума 1968 года по теории коммутации и автоматов, страницы 287–291, Скенектади, Нью-Йорк, 15–18 октября 1968 года. IEEE. Цитаты.
- Шейла А. Грейбах.
- Полные AFL и вложенная итеративная замена.
- В протоколе конференции десятого ежегодного симпозиума по теории коммутации и автоматов 1969 г., страницы 222–230, Ватерлоо, Онтарио, Канада, 15–17 октября 1969 г. IEEE.
- Дж. В. Карлайл, С. А. Грейбах и А. Пас.
- Двумерная генерирующая система, моделирующая рост путем деления двоичных клеток (предварительный отчет).
- На 15-м ежегодном симпозиуме по теории коммутации и автоматов, страницы 1–12, Университет Нового Орлеана, 14–16 октября 1974 г. IEEE.
- С.А. Грейбах.
- Формальные языки: Истоки и направления.
- На 20-м ежегодном симпозиуме по основам информатики , страницы 66–90, Сан-Хуан, Пуэрто-Рико, 29–31 октября 1979 г. IEEE.
Другие
[ редактировать ]- Рональд Бук, Шимон Эвен, Шейла Грейбах и Джин Отт.
- Неоднозначность в графиках и выражениях.
- Транзакции IEEE на компьютерах, том. c-20, № 2, февраль 1971 г. IEEE.
