アルフレッド・エイホ

Alfred V. Aho アルフレッド・V・エイホ
生誕	(1941-08-09) 1941年8月9日（82歳） カナダ オンタリオ州ティミンズ
居住	アメリカ合衆国
国籍	カナダ、 アメリカ合衆国
研究分野	計算機科学
研究機関	コロンビア大学
出身校	トロント大学 プリンストン大学
論文	Indexed Grammars: An Extension of Context Free Grammars (1968)
博士課程 指導教員	ジョン・ホップクロフト
主な受賞歴	IEEE フォン・ノイマンメダル (2003) チューリング賞 (2020)
プロジェクト:人物伝
テンプレートを表示

アルフレッド・ヴァイノ・エイホ（Alfred Vaino Aho、1941年8月9日 - ）は、カナダ出身の計算機科学者。1995年からニューヨークのコロンビア大学で教授を務めており、2003年には同大学同窓会から Great Teacher Award を授与された。

経歴

カナダのトロント大学で応用物理学を学び、アメリカ合衆国のプリンストン大学で電気工学と計算機科学の博士号を取得した。1967年から1991年までベル研究所で研究者として働き、1997年から2002年まで同研究所の計算機科学研究センターの副センター長を務めた。2011年現在、コロンビア大学の計算機科学の教授。1995年から1997年までと、2003年春には同大学計算機科学部門の部門長を務めた。

博士論文で、文脈自由言語のパワーを拡張しつつ決定可能性と閉包特性を保持する indexed grammar^[1] と nested-stack automaton^[2] を生み出した。indexed grammar は並列書き換えシステム、特に生物学関連で使われてきた。

プリンストンを卒業後、ベル研究所の計算機科学研究センターで働きはじめ、効率的な正規表現と文字列のパターンマッチング・アルゴリズムを考案し^[3]、UNIXの egrep と fgrep の最初の実装を行った。fgrep のアルゴリズムはエイホ-コラシック法と呼ばれており、全文検索などで利用されている^[4]。

ベル研究所では、スティーブ・ジョンソンやジェフリー・ウルマンと共にプログラミング言語の解析や変換のための効率的アルゴリズムを研究。ジョンソンはボトムアップのLALR構文解析アルゴリズムを使い^[5]、パーサジェネレータyaccを作った。マイク・レスク（英語版）とエリック・シュミットはエイホのパターンマッチング・アルゴリズムを使い、字句解析器lexを作った。lexとyaccは各種言語のコンパイラ作成に広く使われてきた。

エイホとウルマンはコンパイラ設計についての教科書をいくつか書いている。1977年の Principles of Compiler Design は表紙に緑色のドラゴンが描かれており、"the green dragon book" と呼ばれている。ラビ・セシィ（英語版）も含めた三人で1986年に出版した『コンパイラ—原理・技法・ツール』は原著では赤いドラゴンが描かれた表紙で "the red dragon book" と呼ばれている。2007年にはモニカ・ラムがそれを改訂し "the purple dragon book" と呼ばれている。これらはコンパイラに関する教科書として世界中で読まれてきた。

1974年、エイホとウルマンはジョン・ホップクロフトと共にそれまでのアルゴリズム研究の成果をまとめた『アルゴリズムの設計と解析』を出版した。この本は計算機科学分野で数十年間最も引用・参照されてきた本であり、計算機科学教育でアルゴリズムとデータ構造が重視されるきっかけを作った。

また、ピーター・ワインバーガーおよびブライアン・カーニハンと共にプログラミング言語 AWK を作ったことでもよく知られている（AWK の A は Aho の A）^[6]。

エイホの2010年現在の研究分野は量子コンピュータ、プログラミング言語、コンパイラ、アルゴリズムなどである。コロンビア大学では Language and Compilers research-group に所属している^[7]。

受賞と栄誉

• IEEE フォン・ノイマンメダル（2003年）
• C&C賞（2017年）
• チューリング賞（2020年）

• 全米技術アカデミー会員
• アメリカ芸術科学アカデミーフェロー（2003年）^[8]
• アメリカ科学振興協会フェロー（1986年）
• ACMフェロー（1996年）
• ベル研究所フェロー（1984年）
• IEEEフェロー（1988年）
• ウォータールー大学名誉博士号
• ヘルシンキ大学名誉博士号（1986年）
• Great Teacher Award（コロンビア大学同窓会） （2003年）

また全米科学財団やACMでも役職を務めた。

著作

• ジェフリー・ウルマンとの共著, The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing. Prentice Hall, 1972. ISBN 0-13-914556-7
• 編著 Currents in the Theory of Computing. Prentice Hall, 1973.
• ジェフリー・ウルマンとの共著, The Theory of Parsing, Translation, and Compiling, Vol. 2, Compiling. Prentice-Hall, 1973. ISBN 978-0-13-914564-3
• ジョン・ホップクロフトとの共著, J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN 0-201-00023-7
  • アルゴリズムの設計と解析、サイエンス社、1977年
• ジェフリー・ウルマンとの共著, Principles of Compiler Design. Addison-Wesley, 1977. ISBN 0-201-00022-9
  • コンパイラ（情報処理シリーズ）、培風館、1986年
• ジョン・ホップクロフト, ジェフリー・ウルマンとの共著, Data Structures and Algorithms. Addison-Wesley, 1983. ISBN 0-201-00023-7
  • データ構造とアルゴリズム（情報処理シリーズ）、培風館、1987年
• R. Sethi, ジェフリー・ウルマンとの共著, Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading MA 1986. ISBN 0-201-10088-6
  • 原田賢一 訳、コンパイラ—原理・技法・ツール<1>、サイエンス社、1990年。ISBN 4781905854
  • 原田賢一 訳、コンパイラ—原理・技法・ツール<2>、サイエンス社、1990年。ISBN 4781905862
• ブライアン・カーニハン, and ピーター・ワインバーガーとの共著, The AWK Programming Language. Addison-Wesley, 1988. ISBN 978-0-201-07981-4
  • 足立高穂 訳、プログラミング言語AWK、新紀元社、2004年。ISBN 4775302493
  • プログラミング言語AWK、USP研究所、2010年
• ジェフリー・ウルマンとの共著, Foundations of Computer Science. W. H. Freeman/Computer Science Press, 1992.
• ジェフリー・ウルマンとの共著, Foundations of Computer Science, C Edition. W. H. Freeman, 1995. ISBN 978-0-7167-8284-1
• M. S. Lam（英語版）, R. Sethi（英語版）, ジェフリー・ウルマンとの共著, Compilers: Principles, Techniques, and Tools, Second Edition. Addison-Wesley, 2007. ISBN 978-0-321-48681-3
  • コンパイラ-原理・技法・ツール、第2版、サイエンス社、2009年

出典

関連項目

• エイホ-コラシック法

外部リンク

• Alfred V. Aho's webpage 公式ウェブサイト
• Alfred V. Aho
• Computerworld Interview with Alfred V. Aho
• Alfred Vaino Aho - Mathematics Genealogy Project
• Creating Reliable Programs from Unreliable Programmers [PDF], Excellentia