コンテンツにスキップ

アルフレッド・エイホ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Alfred V. Aho
アルフレッド・V・エイホ
生誕 (1941-08-09) 1941年8月9日(83歳)
カナダの旗 カナダ オンタリオ州ティミンズ
居住 アメリカ合衆国の旗 アメリカ合衆国
国籍 カナダの旗 カナダアメリカ合衆国の旗 アメリカ合衆国
研究分野 計算機科学
研究機関 コロンビア大学
出身校 トロント大学
プリンストン大学
博士論文 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]UNIXegrepfgrep の最初の実装を行った。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]

受賞と栄誉

[編集]

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

著作

[編集]

出典

[編集]
  1. ^ Aho, A.V. (October 1968). “Indexed Grammars — An Extension of Context-Free Grammars”. J. ACM 15 (4): 647–671. doi:10.1145/321479.321488. 
  2. ^ Aho, A.V. (July 1969). “Nested Stack Automata”. J. ACM 16 (3): 383–406. doi:10.1145/321526.321529. 
  3. ^ Aho, A.V.; Corasick, M.J. (June 1975). “Efficient String Matching: an Aid to Bibliographic Search”. Comm. ACM 18 (6): 333–340. doi:10.1145/360825.360855. 
  4. ^ Aho, A.V. (1990). “Algorithms for Finding Patterns in Strings”. Handbook of Theoretical Computer Science. MIT Press. pp. 255–300 
  5. ^ Aho, A.V.; Johnson, S.C.; Ullman, J.D. (January 1977). “Code Generation for Expressions with Common Subexpressions”. J. ACM 24 (1): 146–160. doi:10.1145/321992.322001. 
  6. ^ Aho, A.V.; Kernighan, B.W.; Weinberger, P.J. (April 1979). “AWK — A Pattern Scanning and Processing Language”. Software – Practice and Experience 9 (4): 267–280. doi:10.1002/spe.4380090403. 
  7. ^ Languages and Compilers
  8. ^ Book of Members, 1780-2010: Chapter A”. American Academy of Arts and Sciences. 2011年5月10日時点のオリジナルよりアーカイブ。2011年4月6日閲覧。

関連項目

[編集]

外部リンク

[編集]