Нэнси Энн Линч — американский учёный, профессор компьютерных науки и инженерии Массачусетского технологического института, известная прежде всего автоматами ввода-вывода^[en] — обобщением автоматов Мили на распределённые алгоритмы, позволяющим формально демонстрировать их корректность с помощью иерархических доказательств^[2]. На сегодняшний день существует много разновидностей автоматов ввода-вывода: временны́х^[en], гибридных^[en], вероятностных и динамических^[3], все созданы самой Линч и её сотрудниками. Последними на 2016 год были предложены динамические автоматы ввода-вывода, моделирующие динамические системы и позволяющие создавать и уничтожать автоматы по мере вычисления, что существенно повышает их выразительность^[en] и приближает формализм к современному программному обеспечению. Динамические автоматы ввода-вывода могут объединяться в иерархическую систему, запускаться параллельно, переименовывать и скрывать события, порождать новые автоматы и поддерживать монотонность через семантическую типизацию (если заменить фрагмент автомата на другой, поддерживающий только подмножество последовательностей событий исходного, то на уровне всей системы это может привести только с уменьшению множества возможных последовательностей событий)^[4].

Кроме заметного вклада в теорию автоматов, Нэнси Линч написала несколько книг, среди которых — известный учебник по распределённым алгоритмам^[5], на данный момент слегка устаревший и всё ещё использующийся в учебном процессе, но вытесняемый, например, монографией В. Фоккинка^[6], предлагающей более современный и свежий взгляд на эту быстро развивающуюся область.

Диссертация Нэнси Линч называлась «Релятивизация теории вычислительной сложности» (англ. Relativization of the Theory of Computational Complexity, 1972)^[7]. Линч является автором и соавтором более 100 журнальных и почти 200 конференционных статей^[8]. Она руководила как минимум 28 успешно защитившимися аспирантами^[7]. Она также входит в список членов Академии наук США (с 2015), Инженерной академии^[en] (с 2001)^[9] и Ассоциации вычислительной техники (с 1997)^[10] и является получателем целого ряда престижных академических премий.

Примечания[править | править вики-текст]