Alfred Aho

Last updated

Alfred Aho
Born
Alfred Vaino Aho

(1941-08-09) August 9, 1941 (age 83)
Timmins, Ontario, Canada
NationalityCanadian
American
Alma mater
Known for
Awards
Scientific career
Fields Computer science
Institutions Columbia University
Thesis Indexed Grammars: An Extension of Context Free Grammars  (1968)
Doctoral advisor John Hopcroft [1]
Doctoral students

Alfred Vaino Aho (born August 9, 1941) is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming. [2] [3] [4]

Contents

Aho was elected into the National Academy of Engineering in 1999 for his contributions to the fields of algorithms and programming tools.

He and his long-time collaborator Jeffrey Ullman are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science. [5]

Career

Aho received a B.A.Sc. (1963) in Engineering Physics from the University of Toronto, then an M.A. (1965) and Ph.D. (1967) in Electrical Engineering/Computer Science from Princeton University. [6] He conducted research at Bell Labs from 1967 to 1991, and again from 1997 to 2002 as Vice President of the Computing Sciences Research Center. [7] Since 1995, he has held the Lawrence Gussman Professorship in Computer Science at Columbia University. He served as chair of the department from 1995 to 1997, and again in the spring of 2003. [8]

In his PhD thesis Aho created indexed grammars [9] and the nested-stack automaton [10] as vehicles for extending the power of context-free languages, but retaining many of their decidability and closure properties. One application of indexed grammars is modelling parallel rewriting systems, [11] particularly in biological applications. [12]

After graduating from Princeton, Aho joined the Computing Sciences Research Center at Bell Labs where he devised efficient regular expression and string-pattern matching algorithms that he implemented in the first versions of the Unix tools egrep and fgrep . The fgrep algorithm has become known as the Aho–Corasick algorithm; it is used by several bibliographic search-systems, including the one developed by Margaret J. Corasick, and by other string-searching applications. [13]

At Bell Labs, Aho worked closely with Steve Johnson and Jeffrey Ullman to develop efficient algorithms for analyzing and translating programming languages. [14] Steve Johnson used the bottom-up LALR parsing algorithms to create the syntax-analyzer generator yacc, [15] and Michael E. Lesk and Eric Schmidt used Aho's regular-expression pattern-matching algorithms to create the lexical-analyzer generator lex. [16] The lex and yacc tools and their derivatives have been used to develop the front ends of many of today's programming language compilers. [17]

Aho and Ullman wrote a series of textbooks on compiling techniques that codified the theory relevant to compiler design. Their 1977 textbook Principles of Compiler Design had a green dragon on the front cover and became known as "the green dragon book". In 1986 Aho and Ullman were joined by Ravi Sethi to create a new edition, "the red dragon book" (which was briefly shown in the 1995 movie Hackers ), and in 2006 also by Monica Lam to create "the purple dragon book". The dragon books are used for university courses as well as industry references. [18]

In 1974, Aho, John Hopcroft, and Ullman wrote The Design and Analysis of Computer Algorithms, [19] codifying some of their early research on algorithms. This book became one of the most highly cited books in computer science for several decades and helped to stimulate the creation of algorithms and data structures as a central course in the computer science curriculum. [20]

Aho is also widely known for his co-authorship of the AWK programming language with Peter J. Weinberger and Brian Kernighan (the "A" stands for "Aho"). [21] As of 2010 Aho's research interests include programming languages, compilers, algorithms, and quantum computing. He is part of the Language and Compilers research-group at Columbia University. [22]

Overall, his works have been cited 81,040 times and he has an h-index of 66, as of May 8, 2019. [23]

Aho has received many prestigious honors, including the IEEE's John von Neumann Medal and membership in the National Academy of Engineering and the National Academy of Sciences. He was elected a Fellow of the American Academy of Arts and Sciences in 2003. [24] He holds honorary doctorates from the University of Waterloo, [25] from the University of Helsinki, [25] and from the University of Toronto. [26] He is a Fellow of the American Association for the Advancement of Science, ACM, Bell Labs, and IEEE. [20]

Aho has twice served as chair of the Advisory Committee for the Computer and Information Science and Engineering Directorate of the National Science Foundation. He is a past president of the ACM Special Interest Group on Algorithms and Computability Theory. [27] Aho, Hopcroft, and Ullman were co-recipients of the 2017 C&C Prize awarded by NEC Corporation. [28] He and Ullman were named recipients of the 2020 Turing Award on March 31, 2021. [5]

Personal life

Aho has taught at Columbia University in New York City since 1995. He won the Great Teacher Award from the Society of Columbia Graduates in 2003. [29] [30]

Books

Related Research Articles

In computing, a compiler is a computer program that translates computer code written in one programming language into another language. The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language to create an executable program.

<span class="mw-page-title-main">Finite-state machine</span> Mathematical model of computation

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed.

In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.

<span class="mw-page-title-main">Turing Award</span> American annual computer science prize

The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the field of computer science and is often referred to as the "Nobel Prize of Computing".

<i>Compilers: Principles, Techniques, and Tools</i> Computer science compiler technology textbook

Compilers: Principles, Techniques, and Tools is a computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction for programming languages. First published in 1986, it is widely regarded as the classic definitive compiler technology text.

<i>Principles of Compiler Design</i> Book by Alfred Aho and Jeffrey Ullman

Principles of Compiler Design, by Alfred Aho and Jeffrey Ullman, is a classic textbook on compilers for computer programming languages. Both of the authors won the 2020 Turing award for their work on compilers.

<span class="mw-page-title-main">John Hopcroft</span> American computer scientist (born 1939)

John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is a professor emeritus at Cornell University, co-director of the Center on Frontiers of Computing Studies at Peking University, and the director of the John Hopcroft Center for Computer Science at Shanghai Jiao Tong University.

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

Jeffrey David Ullman is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers, theory of computation, data structures, and databases are regarded as standards in their fields. He and his long-time collaborator Alfred Aho are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

Seymour Ginsburg was an American pioneer of automata theory, formal language theory, and database theory, in particular; and computer science, in general. His work was influential in distinguishing theoretical Computer Science from the disciplines of Mathematics and Electrical Engineering.

<span class="mw-page-title-main">Computational complexity of mathematical operations</span> Algorithmic runtime requirements for common math procedures

The following tables list the computational complexity of various algorithms for common mathematical operations.

Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.

<span class="mw-page-title-main">David Gries</span> American computer scientist

David Gries is an American computer scientist at Cornell University, mainly known for his books The Science of Programming (1981) and A Logical Approach to Discrete Math.

In computer science, the Hunt–Szymanski algorithm, also known as Hunt–McIlroy algorithm, is a solution to the longest common subsequence problem. It was one of the first non-heuristic algorithms used in diff which compares a pair of files each represented as a sequence of lines. To this day, variations of this algorithm are found in incremental version control systems, wiki engines, and molecular phylogenetics research software.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

A lookahead LR parser (LALR) generator is a software tool that reads a context-free grammar (CFG) and creates an LALR parser which is capable of parsing files written in the context-free language defined by the CFG. LALR parsers are desirable because they are very fast and small in comparison to other types of parsers.

In computer science, the Method of Four Russians is a technique for speeding up algorithms involving Boolean matrices, or more generally algorithms involving matrices in which each cell may take on only a bounded number of possible values.

References

  1. ↑ Alfred Vaino Aho at the Mathematics Genealogy Project
  2. ↑ Aho, A.; Gottlob, G. (2014). "A front row seat to Communications' editorial transformation". Communications of the ACM. 57 (4): 5. doi:10.1145/2582611. S2CID   21553189.
  3. ↑ Aho, A.V. (1990). "Algorithms for Finding Patterns in Strings". Handbook of Theoretical Computer Science. MIT Press. pp. 255–300.
  4. ↑ "IT news, careers, business technology, reviews". Computerworld. Archived from the original on May 29, 2008. Retrieved May 18, 2023.
  5. 1 2 ACM Turing Award Honors Innovators Who Shaped the Foundations of Programming Language Compilers and Algorithms. Retrieved March 31, 2021.
  6. ↑ "Creating Reliable Programs from Unreliable Programmers" (PDF). Excellentia.
  7. ↑ Fitchard, Kevin (March 31, 2021). "Bell Labs' Al Aho and Jeffrey Ullman honored with the prestigious Turing Award". Nokia Bell Labs. Archived from the original on April 1, 2021. Retrieved April 3, 2021.
  8. ↑ "Profile and Detailed Achievements of the Group B Recipients of the 2017 C&C Prize" (PDF). The NEC C&C Foundation. Archived (PDF) from the original on January 20, 2022.
  9. ↑ Aho, A. V. (1968). "Indexed Grammars—An Extension of Context-Free Grammars". Journal of the ACM. 15 (4): 647–671. doi: 10.1145/321479.321488 . S2CID   9539666.
  10. ↑ Aho, A. V. (1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi: 10.1145/321526.321529 . S2CID   685569.
  11. ↑ Rambow, Owen; Satta, Giorgio (July 28, 1999). "Independent parallelism in finite copying parallel rewriting systems". Theoretical Computer Science. 223 (1–2): 87–120. doi:10.1016/S0304-3975(97)00190-4. ISSN   0304-3975.
  12. ↑ Culik, Karel; Maibaum, T. S. E. (1974). "Parallel Rewriting Systems on Terms". In Loeckx, Jacques (ed.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 14. Berlin, Heidelberg: Springer. pp. 495–510. doi:10.1007/978-3-662-21545-6_38. ISBN   978-3-662-21545-6.
  13. ↑ Aho, Alfred V.; Corasick, Margaret J. (June 1975). "Efficient String Matching: An Aid to Bibliographic Search". Communications of the ACM . 18 (6): 333–340. doi: 10.1145/360825.360855 . S2CID   207735784.
  14. ↑ Aho, A. V.; Johnson, S. C.; Ullman, J. D. (1977). "Code Generation for Expressions with Common Subexpressions". Journal of the ACM. 24: 146–160. doi: 10.1145/321992.322001 . S2CID   2614214.
  15. ↑ Morris, Richard (October 1, 2009). "Stephen Curtis Johnson: Geek of the Week". Red Gate Software. Retrieved January 19, 2018.
  16. ↑ Lesk, M.E.; Schmidt, E. "Lex – A Lexical Analyzer Generator" . Retrieved August 16, 2010.
  17. ↑ Levine, John R.; Mason, Tony; Brown, Doug (1992). lex & yacc (2 ed.). O'Reilly. pp.  1–2. ISBN   1-56592-000-7.
  18. ↑ "DYOL: Design Your Own Language — corpus — Dragon Books — Purple Dragon". slebok.github.io. Retrieved April 3, 2021.
  19. ↑ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN   978-0-201-00029-0.
  20. 1 2 Ibaraki, Stephen. "Jeffrey Ullman And Alfred Aho, 2020 ACM A.M.Turing Award Recipients". forbes.com. Retrieved April 3, 2021.
  21. ↑ Aho, A. V.; Kernighan, B. W.; Weinberger, P. J. (1979). "Awk — a pattern scanning and processing language". Software: Practice and Experience. 9 (4): 267. CiteSeerX   10.1.1.80.4787 . doi:10.1002/spe.4380090403. S2CID   29399630.
  22. ↑ "Languages and Compilers". landc.cs.columbia.edu. Retrieved May 18, 2023.
  23. ↑ "Google Scholar Record for Alfred Aho".
  24. ↑ "Book of Members, 1780–2010: Chapter A" (PDF). American Academy of Arts and Sciences. Archived (PDF) from the original on May 10, 2011. Retrieved April 6, 2011.
  25. 1 2 "DLS – Alfred Aho". Cheriton School of Computer Science. February 16, 2017. Retrieved April 3, 2021.
  26. ↑ Do, Liz. "'Nobel Prize of computing:' U of T Engineering alumnus Alfred Aho receives A.M. Turing Award". utoronto.ca. Retrieved April 3, 2021.
  27. ↑ "Brief U.S. Suppression of Proof Stirs Anger". The New York Times. February 17, 1987. Retrieved November 10, 2015– via Safari.
  28. ↑ "2017 C&C Prize Ceremony". NEC C&C Foundation. Archived from the original on July 10, 2018. Retrieved April 3, 2021.
  29. ↑ "Watch: Computer Scientist Alfred Aho". Simons Foundation. July 18, 2013. Retrieved April 3, 2021.
  30. ↑ "Master Recipient List". Society of Columbia Graduates. Retrieved April 15, 2023.
  31. ↑ Currents in the theory of computing, edited by Alfred V. Aho. Contributing authors: Ronald V. Book [and others]. OCLC   976868524 . Retrieved April 1, 2021– via worldcat.org.
  32. ↑ Foundations of computer science. OCLC   24669768 . Retrieved April 1, 2021– via worldcat.org.
  33. ↑ Foundations of computer science. OCLC   797873166 . Retrieved April 1, 2021– via worldcat.org.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.