Шейла Грейбах - Sheila Greibach
 | Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
Шейла Грейбах | |
|---|---|
| Родился | 6 октября 1939 г. |
| Альма-матер | Рэдклифф Колледж Гарвардский университет |
| Известен | Нормальная форма Грейбаха, Теорема Грейбаха |
| Научная карьера | |
| Поля | Теоретическая информатика Формальный язык в вычислительной технике Автоматы Вычислительная сложность Теория компилятора |
| Учреждения | Калифорнийский университет в Лос-Анджелесе Гарвардский университет |
| Докторант | Энтони Эттингер |
| Докторанты | Рональд В. Книга, Майкл Дж. Фишер, Жан Галье |
Шейла Адель Грейбах (родился 6 октября 1939 года в Нью-Йорке), исследователь в формальные языки в вычислениях, автоматы, компилятор теория и Информатика. Она заслуженный профессор Информатика на Калифорнийский университет в Лос-Анджелесе, и заметная работа включает работу с Сеймур Гинзбург и Майкл А. Харрисон в контекстно-зависимый анализ с использованием стековый автомат модель.
Помимо установления нормальной формы (Нормальная форма Грейбаха ) для контекстно-свободные грамматики, в 1965 году она также исследовала свойства W-грамматики, выталкивающие автоматы, и проблемы разрешимости.
Ранняя карьера
Грейбах получил A.B. степень (с отличием ) в Лингвистика и Прикладная математика из Рэдклифф Колледж в 1960 году, а через два года после того, как получил премию A.M. степень. В 1963 г. ей была присуждена степень доктора философии в г. Гарвардский университет, посоветовал Энтони Эттингер[1] защитил кандидатскую диссертацию на тему "Инверсии генераторов структуры фраз".
Она продолжала работать в Гарварде в отделе инженерии и прикладной физики до 1969 года, когда она переехала в UCLA, где является профессором по настоящее время (по состоянию на март 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 г.
- Показано, что проблема того, является ли данный контекстно-свободный язык линейным, рекурсивно неразрешима.
Соавторские работы
"Multitape AFA" в соавторстве с Сеймуром Гинзбургом, Журнал ACM, Том 19, выпуск 2, апрель 1972 г.
"Супердетерминированные КПК: подслучай с разрешимой проблемой включения", в соавторстве с Э. П. Фридманом "JACM ", Октябрь 1980 г., том 27, выпуск 4
"Стековые автоматы и компиляция", в соавторстве с Сеймуром Гинзбургом и Майклом А. Харрисоном "JACM ", Январь 1967 г., том 14, выпуск 1
- Составление состоит из двух частей: распознавания и перевода. Представлена математическая модель, которая воплощает характерные черты многих современных методов компиляции. Модель, называемая автоматом стека, имеет желаемое свойство детерминированности по своей природе. Это детерминированное устройство обобщается до недетерминированного устройства (недетерминированного стекового автомата), и отмечаются конкретные примеры этого более общего устройства. Множества, принимаемые недетерминированными стековыми автоматами, являются рекурсивными ...
"Языки квази-реального времени (расширенное резюме)", в соавторстве с Рональдом В. Книга, Труды первого ежегодного симпозиума ACM по теории вычислений, май 1969 г.
- Языки квази-реального времени - это языки, приемлемые для недетерминированной многоленты. Машины Тьюринга в реальном времени. Семейство языков квазиреального времени образует абстрактное семейство языков, замкнутых при пересечении, линейном стирании и обращении. Он идентичен семейству языков, принимаемых недетерминированными многоленточными машинами Тьюринга за линейное время. Каждый язык квази-реального времени может быть принят в реальном времени недетерминированным одним стеком, одной машиной с расширяющимся хранилищем и может быть е ...
«Автомат с односторонним стеком», в соавторстве с Сеймуром Гинзбургом и Майклом А. Харрисоном »JACM ", Апрель 1967 г., том 14, выпуск 2
- Представлен ряд операций, которые либо сохраняют множества, принятые односторонними стековыми автоматами, либо сохраняющие множества, принятые детерминированными односторонними стековыми автоматами. Например, последовательная трансдукция сохраняет первое; набор дополнений, последний. Рассмотрены также некоторые вопросы разрешимости.
«Тьюринговые акцепторы и AFL с ограничением по времени и лентой (расширенное резюме)» в соавторстве с Рональдом В. Буком и Беном Вегбрайтом, Труды второго ежегодного симпозиума ACM по теории вычислений, май 1970 г.
- Классы сложности формальных языков, определяемые акцепторами Тьюринга, ограниченными по времени и лентой, изучаются с целью показать достаточные условия для того, чтобы эти классы были AFL и главными AFL.
"Uniformly erasable AFL", в соавторстве с Сеймуром Гинзбургом и Джонатаном Голдстайном, Труды четвертого ежегодного симпозиума ACM по теории вычислений, май 1972 г.
- В этой статье показано, что ряд известных семейств обладают свойством (*). В частности, авторы доказали, что семейство контекстно-свободных языков действительно обладает этим свойством. Кроме того, мы показываем, что несколько знакомых подсемейств контекстно-свободных языков, таких как языки с одним счетчиком, иметь свойство (*). Наконец, мы показываем, что существуют семейства, удовлетворяющие (*), которые не являются подсемействами контекстно-свободных языков, поскольку мы доказываем, что любое семейство, порожденное одним let ...[требуется разъяснение ]
- Формальные системы парсинга
- Шейла А. Грейбах
- Август 1964 г.
- Коммуникации ACM, Том 7 Выпуск 8
- Автоматический синтаксический анализ в последнее время стал важен как для естественный язык обработка данных и ориентированный на синтаксис компиляторы. Формальная система синтаксического анализа G = (V, μ, T, R) состоит из двух конечных непересекающихся словарей, V и T, отображения многих-многих, μ, из V в T, и рекурсивного набора R строк в T, называемого синтаксическим классы предложений ...
Из библиографии FOCS
- Сеймур Гинзбург и Шейла Грейбах.
- Детерминированные контекстно-свободные языки.
- В материалах шестого ежегодного Симпозиум по теории коммутационных цепей и логическому проектированию, страницы 203-220. IEEE, 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.
- J. W. Carlyle, S.A. Greibach и A. Paz.
- Двухмерная генерирующая система, моделирующая рост путем бинарного деления клеток (предварительный отчет).
- На 15-м ежегодном симпозиуме по теории переключений и автоматов, страницы 1–12, Университет Нового Орлеана, 14–16 октября 1974 г. IEEE.
- С. А. Грейбах.
- Формальные языки: истоки и направления.
- В 20-м ежегодном Симпозиум по основам информатики, страницы 66–90, Сан-Хуан, Пуэрто-Рико, 29–31 октября 1979 г. IEEE.
Другие
- Рональд Бук, Шимон Эвен, Шейла Грейбах и Джин Отт.
- Неоднозначность графиков и выражений.
- IEEE Transactions on Computers, vol. c-20, No. 2, февраль 1971 г. IEEE.
