stringtranslate.com

Рональд Фейгин

Рональд Фейгин (родился в 1945 году) — американский математик и учёный-компьютерщик , а также научный сотрудник IBM в исследовательском центре IBM Almaden . Он известен своими работами в области теории баз данных , теории конечных моделей и рассуждений о знаниях. [1]

Биография

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

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

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

Фейгин получил множество профессиональных наград за свою работу. Он является членом Национальной академии наук , Национальной инженерной академии и Американской академии искусств и наук . Он является членом IBM , членом ACM , членом IEEE , членом Американской ассоциации содействия развитию науки и членом Азиатско-Тихоокеанской ассоциации искусственного интеллекта. Одна из его работ [2] получила премию Гёделя . Он получил степень Docteur Honoris Causa от Парижского университета и степень Laurea Honoris Causa от Калабрийского университета в Италии. IEEE вручил ему премию IEEE W. Wallace McDowell Award и премию IEEE за технические достижения [3] (теперь известную как премия Edward J. McCluskey за технические достижения [4] ); и ACM присудил ему премию ACM SIGMOD Edgar F. Codd Innovations Award Европейская ассоциация теоретической информатики (совместно с ACM Special Interest Group for Logic and Computation, European Association for Computer Science Logic и Kurt Gödel Society) присудила ему и соавторам двух его статей [5] [6] премию Алонзо Чёрча за логику и вычисления . IBM присудила ему восемь премий IBM Outstanding Innovation Awards, две премии IBM supplemental Patent Issue Awards, присуждаемые за ключевые патенты IBM, три премии IBM Outstanding Technical Achievement Awards и две корпоративные премии IBM. Он получил награды за лучшую статью на Международной совместной конференции по искусственному интеллекту 1985 года, симпозиуме ACM 2001 года по принципам систем баз данных, Международной конференции по теории баз данных 2010 года и Международной конференции по теории баз данных 2015 года. Он получил награду «10-летняя проверка временем» на симпозиуме ACM по принципам систем баз данных 2011 года, на Международной конференции по теории баз данных 2013 года и на симпозиуме ACM по принципам систем баз данных 2014 года.

Работа

Теорема Фейгина

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

Другие вклады

Другой результат, который он доказал в своей докторской диссертации, заключается в том, что логика первого порядка имеет закон нуля или единицы, который гласит, что если S — предложение первого порядка, содержащее только реляционные символы (без функциональных или константных символов), то доля структур n-узлов, удовлетворяющих S, сходится при n, стремящемся к бесконечности, и фактически сходится к 0 или 1. [9] Этот результат был независимо доказан Глебским и соавторами ранее (1969) в России [10] с совершенно другим доказательством.

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

Помимо теоремы Фейгина, в честь Фейгина названы и другие концепции: «алгоритм Фейгина» для агрегации оценок [11] , «обратный алгоритм Фейгина» для обмена данными [12] , а также «игры Фейгина» [13] и «игры Аджтая–Фейгина» [14] для доказательства невыразимости результатов в логике.

Публикации

Фейгин является автором и соавтором множества статей [15] [16] и книги:

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

Ссылки

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

Внешние ссылки