Рональд Феджин - Ronald Fagin

Рональд Феджин
Рональд Фэджин, IBM Researcher.jpg
Рональд Феджин
Родившийся1945[1]
Оклахома-Сити, Ok, СОЕДИНЕННЫЕ ШТАТЫ АМЕРИКИ
НациональностьАмериканец
Альма-матерДартмутский колледж,
Калифорнийский университет в Беркли
ИзвестенТеорема Феджина
НаградыПриз Гёделя (2014),
Премия Уоллеса Макдауэлла (2012),
SIGMOD Премия Эдгара Ф. Кодда за инновации (2004)
Научная карьера
ПоляЛогика в информатике,
Теория баз данных,
Теория конечных моделей,
Агрегирование рангов и оценок,
Рассуждения о знаниях
УчрежденияИсследовательский центр IBM в Альмадене
ДокторантРоберт Лоусон Воот

Рональд Феджин (1945 г.р.) - американец математик и специалист в области информатики, и Сотрудник IBM на Исследовательский центр IBM в Альмадене. Он известен своей работой в теория баз данных, теория конечных моделей, и рассуждения о знаниях.[2]

биография

Рон Феджин родился и вырос в Оклахома-Сити, где он присутствовал Северо-западная классическая средняя школа. После этого он получил степень бакалавра в Дартмутский колледж. Феджин получил докторскую степень. по математике из Калифорнийский университет в Беркли в 1973 г., где работал под руководством Роберт Воот.

Он присоединился к IBM Research Дивизии в 1973 году, проведя два года в Исследовательский центр Томаса Дж. Уотсона, а затем переведен в 1975 году на то, что сейчас Исследовательский центр IBM в Альмадене в Сан-Хосе, Калифорния.

Он работал председателем программного комитета симпозиума ACM по принципам систем баз данных 1984,[3] Теоретические аспекты рассуждений о знаниях 1994,[4] Симпозиум ACM по теории вычислений 2005 г.,[5] и Международная конференция по теории баз данных 2009 г.[6]

За свою работу Феджин получил множество профессиональных наград. Он является членом Национальная Академия Наук, Национальная инженерная академия, и Американская академия искусств и наук. Он Сотрудник IBM, Член ACM, IEEE Сотрудник и научный сотрудник Американская ассоциация развития науки. Одна из его работ [7] выиграл Премия Гёделя. Он получил Docteur Honoris Causa от Парижский университет, и Laurea Honoris Causa из Университет Калабрии в Италии. IEEE предоставил ему IEEE Премия Уоллеса Макдауэлла и награда IEEE за технические достижения [8] (теперь известная как Премия Эдварда Дж. Маккласки за технические достижения [9]); и ACM предоставил ему награду ACM SIGMOD Edgar F. Codd Innovations Award.[10]. Европейская ассоциация теоретической информатики (совместно со Специальной группой ACM по логике и вычислениям, Европейской ассоциацией логики компьютерных наук и Обществом Курта Гёделя) предоставила ему и соавторам двух его статей [11], [12] Премия Алонзо Черча в области логики и вычислений [13]. IBM вручила ему восемь наград IBM за выдающиеся инновации, две дополнительные награды IBM за выдачу патентов за ключевые патенты IBM, три награды IBM за выдающиеся технические достижения и две корпоративные награды IBM. Он получил награду за лучшую работу на Международной совместной конференции по искусственному интеллекту в 1985 году, на симпозиуме ACM 2001 года по принципам систем баз данных, на Международной конференции по теории баз данных 2010 года и на Международной конференции по теории баз данных 2015 года. Он выиграл 10-летнюю награду Test-of-Time Awards на симпозиуме ACM 2011 г. по принципам систем баз данных, Международной конференции по теории баз данных 2013 г. и симпозиуме ACM 2014 г. по принципам систем баз данных.

Работа

Теорема Феджина

Теорема Феджина, что он доказал в своей докторской диссертации, утверждает, что экзистенциальные логика второго порядка совпадает с классом сложности НП в том смысле, что проблема решения может быть выражена в экзистенциальной логике второго порядка тогда и только тогда, когда она может быть решена недетерминированная машина Тьюринга за полиномиальное время. Эта работа помогла основать район теория конечных моделей.[14] [15]

Прочие взносы

Еще один результат, который он доказал в своей докторской диссертации, заключается в том, что логика первого порядка имеет закон нуля или единицы, инструмент для доказательства невыразимости результатов для языков запросов к базам данных.[16] Этот результат был независимо доказан Глебским и др. ранее (1969) в России,[17] с совсем другим доказательством.

Он также известен своей работой над высшими нормальные формы в теория баз данных, особенно 4NF, 5NF и DK / NF.

Помимо теоремы Фейгина, другие концепции, названные в честь Феджина, представляют собой «алгоритм Феджина» для агрегирования оценок,[18] «обратный Феджину» для обмена данными,[19] и «Фэджинские игры» [20] и "Игры Айтай Фэджин" [21] для доказательства невыразимости результатов в логике.

Публикации

Феджин является автором или соавтором множества статей,[22][23] и книга:

  • Рональд Феджин, Джозеф И. Халперн, Йорам Мозес и Моше Ю. Варди. Рассуждения о знаниях. MIT press (1995). Издание в мягкой обложке (2003 г.).

Статьи, подборка:

Рекомендации

  1. ^ Американские мужчины и женщины науки, Томсон Гейл, 2004.
  2. ^ Рональд Феджин, Джозеф И. Халперн, Йорам Мозес и Моше Ю. Варди, Рассуждения о знаниях, MIT Press, 1995. Издание в мягкой обложке, 2003.
  3. ^ Симпозиум ACM по принципам систем баз данных 1984
  4. ^ Теоретические аспекты рассуждений о знаниях 1994 г.
  5. ^ Симпозиум по теории вычислений 2005 г.
  6. ^ Международная конференция по теории баз данных 2009
  7. ^ Рональд Феджин, Амнон Лотем и Мони Наор., «Оптимальные алгоритмы агрегирования для промежуточного программного обеспечения». Журнал компьютерных и системных наук 66 (2003): 614-656. Расширенная аннотация появилась в Proc. Симпозиум ACM 2001 г. по принципам систем баз данных, стр. 102-113.
  8. ^ Компьютерное общество IEEE назвало победителей технических достижений 2011 года
  9. ^ Премия Эдварда Дж. Маккласки за технические достижения
  10. ^ ACM SIGMOD Премия Эдгара Ф. Кодда за инновации
  11. ^ Рональд Феджин, Фокион Колайтис, Рене Дж. Миллер и Лучиан Попа, «Обмен данными: семантика и ответы на запросы», Теоретическая информатика 336 (2005): 89-124. (Специальный выпуск для избранных статей с Международной конференции по теории баз данных 2003 г.).
  12. ^ Рональд Фэджин, Фокион Г. Колайтис, Лучиан Попа и Ван-Чью Тан, «Составление сопоставлений схем: на помощь приходят зависимости второго порядка», ACM Trans. on Database Systems 30, 4 (декабрь 2005 г.), стр. 994-1055. (Специальный выпуск для избранных статей с конференции ACM SIGMOD / PODS 2004 г.).
  13. ^ Премия церкви Алонсо 2020 года
  14. ^ Нил Иммерман, Описательная сложность. Springer-Verlag, 1999.
  15. ^ Леонид Либкин, Элементы теории конечных моделей. Springer 2004. ISBN  978-3-540-21202-7.
  16. ^ Рональд Феджин: "Вероятности на конечных моделях ". Journal of Symbolic Logic, 41 (1): 50-58, 1976
  17. ^ Ю.В. Глебский, Д. Коган, М. Лёгонький, В.А. Таланов: "Диапазон и степень реализуемости формул в ограниченном исчислении предикатов. »Кибернетика, 2: 17-28, 1969.
  18. ^ Рональд Феджин. "Объединение нечеткой информации из нескольких систем. "Journal of Computer and System Sciences 58 (1999): 83-99. (Специальный выпуск для избранных статей с Симпозиума ACM 1996 г. по принципам систем баз данных).
  19. ^ Рональд Феджин "Инвертирование сопоставлений схемы ". ACM Trans. On Database Systems 32, 4, Nov. 2007. (Специальный выпуск для избранных статей с Симпозиума ACM 2006 г. по принципам систем баз данных.)
  20. ^ Рональд Феджин "Монадические обобщенные спектры ". Zeitschr. F. Math. Logik und Grundlagen d. Math. 21, 1975, стр. 89-96.
  21. ^ Миклош Айтай и Рональд Феджин "Для ориентированных конечных графов достижимость сложнее, чем для неориентированных конечных графов. ". Journal of Symbolic Logic 55, 1, March 1990, pp. 113-150. Предварительная версия появилась в Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 358-367.
  22. ^ Рональд Феджин: Исследовательский центр IBM Almaden Профиль Google Scholar
  23. ^ Рональд Феджин Библиография DBLP по информатике

внешняя ссылка