Alfred Vaino Aho (born August 9, 1941) is a Canadian

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

best known for his work on

programming language A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...

compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...

s, and related algorithms, and his textbooks on the art and science of computer programming. Aho was elected into the

National Academy of Engineering The National Academy of Engineering (NAE) is an American Nonprofit organization, nonprofit, NGO, non-governmental organization. It is part of the National Academies of Sciences, Engineering, and Medicine (NASEM), along with the National Academ ...

in 1999 for his contributions to the fields of algorithms and programming tools. He and his long-time collaborator

Jeffrey Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dr ...

are the recipients of the 2020

Turing Award 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 fi ...

, generally recognized as the highest distinction in

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

Career

Aho received a B.A.Sc. (1963) in Engineering Physics from the

University of Toronto The University of Toronto (UToronto or U of T) is a public university, public research university whose main campus is located on the grounds that surround Queen's Park (Toronto), Queen's Park in Toronto, Ontario, Canada. It was founded by ...

, then an M.A. (1965) and Ph.D. (1967) in Electrical Engineering/Computer Science from

Princeton University Princeton University is a private university, private Ivy League research university in Princeton, New Jersey, United States. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial ...

. He conducted research at

Bell Labs Nokia Bell Labs, commonly referred to as ''Bell Labs'', is an American industrial research and development company owned by Finnish technology company Nokia. With headquarters located in Murray Hill, New Jersey, Murray Hill, New Jersey, the compa ...

from 1967 to 1991, and again from 1997 to 2002 as Vice President of the Computing Sciences Research Center. Since 1995, he has held the Lawrence Gussman Professorship in

Computer Science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

Columbia University Columbia University in the City of New York, commonly referred to as Columbia University, is a Private university, private Ivy League research university in New York City. Established in 1754 as King's College on the grounds of Trinity Churc ...

. He served as chair of the department from 1995 to 1997, and again in the spring of 2003. In his PhD thesis Aho created

indexed grammar Indexed grammars are a generalization of context-free grammars in that nonterminals are equipped with lists of ''flags'', or ''index symbols''. The language produced by an indexed grammar is called an indexed language. Definition Modern definiti ...

s and the nested-stack automaton as vehicles for extending the power of

context-free languages In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most ...

, but retaining many of their decidability and closure properties. One application of indexed grammars is modelling parallel rewriting systems, particularly in biological applications. After graduating from Princeton, Aho joined the Computing Sciences Research Center at Bell Labs where he devised efficient

regular expression A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...

and string-pattern matching algorithms that he implemented in the first versions of the

Unix Unix (, ; trademarked as UNIX) is a family of multitasking, multi-user computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, a ...

tools

egrep 


grep is a  command-line utility for searching plaintext datasets for lines that match a regular expression. Its name comes from the  ed command g/re/p (global regular expression search and print), which has the same effect. grep was originally de ...

and

fgrep 


grep is a command line interface, command-line utility for searching plaintext datasets for lines that match a regular expression. Its name comes from the ed (text editor), ed command g/re/p (global regular expression search and print), which has ...

. The fgrep algorithm has become known as the

Aho–Corasick algorithm In computer science, the Aho–Corasick algorithm is a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "di ...

; it is used by several bibliographic search-systems, including the one developed by Margaret J. Corasick, and by other string-searching applications. At Bell Labs, Aho worked closely with Steve Johnson and

to develop efficient algorithms for analyzing and translating programming languages. Steve Johnson used the bottom-up LALR parsing algorithms to create the syntax-analyzer generator

yacc Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a lookahead left-to-right rightmost derivation (LALR) parser generator, generating a LALR parser (the part of a co ...

, and

Michael E. Lesk Michael E. Lesk (born 1945) is an American computer scientist. Biography In the 1960s, Michael Lesk worked for the SMART Information Retrieval System project, wrote much of its retrieval code and did many of the retrieval experiments, as well as ...

and

Eric Schmidt Eric Emerson Schmidt (born April 27, 1955) is an American businessman and former computer engineer who was the chief executive officer of Google from 2001 to 2011 and the company's chairman, executive chairman from 2011 to 2015. He also was the ...

used Aho's regular-expression pattern-matching algorithms to create the lexical-analyzer generator

lex Lex or LEX may refer to: Computing * Amazon Lex, a service for building conversational interfaces into any application using voice and text * LEX (cipher), a stream cipher based on the round transformation of AES * Lex (software), a computer pro ...

. The lex and yacc tools and their derivatives have been used to develop the front ends of many of today's programming language compilers. 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 ''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. It is often called the "green ...

'' 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 Ravi Sethi (born 1947) is an Indian computer scientist retired from executive roles at Bell Labs and Avaya Labs. He also serves as a member of the National Science Foundation's Computer and Information Science and Engineering (CISE) Advisory C ...

to create a new edition, "the red dragon book" (which was briefly shown in the 1995 movie ''

Hackers A hacker is a person skilled in information technology who achieves goals and solves problems by non-standard means. The term has become associated in popular culture with a security hackersomeone with knowledge of bugs or exploits to break ...

''), and in 2006 also by

Monica Lam Monica Sin-Ling Lam is an American computer scientist. She is a professor in the Computer Science Department at Stanford University. Education Monica Lam received a B.Sc. from University of British Columbia in 1980 and a Ph.D. in computer scien ...

to create "the purple dragon book". The dragon books are used for university courses as well as industry references. In 1974, Aho,

John Hopcroft John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is a professo ...

, and Ullman wrote ''The Design and Analysis of Computer Algorithms'', 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 structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

s as a central course in the computer science curriculum. Aho is also widely known for his co-authorship of the AWK programming language with

Peter J. Weinberger Peter Jay Weinberger (born August 6, 1942) is a computer scientist best known for his early work at Bell Labs. He now works at Google. Weinberger was an undergraduate at Swarthmore College, graduating in 1964. He received his PhD in mathematics ...

and

Brian Kernighan Brian Wilson Kernighan (; born January 30, 1942) is a Canadian computer scientist. He worked at Bell Labs and contributed to the development of Unix alongside Unix creators Ken Thompson and Dennis Ritchie. Kernighan's name became widely known ...

(the "A" stands for "Aho"). Aho's research interests include programming languages, compilers, algorithms, and

quantum computing A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of wave-particle duality, both particles and waves, and quantum computing takes advantage of this behavior using s ...

. He is part of the Language and Compilers research-group at Columbia University. Overall, his works have been cited 81,040 times and he has an

h-index The ''h''-index is an author-level metric that measures both the productivity and citation impact of the publications, initially used for an individual scientist or scholar. The ''h''-index correlates with success indicators such as winning t ...

of 66, as of May 8, 2019. Aho has received many prestigious honors, including the

IEEE The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) organization, 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and other related disciplines. The IEEE ...

John von Neumann Medal The IEEE John von Neumann Medal was established by the IEEE Board of Directors in 1990 and may be presented annually "for outstanding achievements in computer-related science and technology." The achievements may be theoretical, technological, or ...

and membership in the

and the

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...

. He was elected a Fellow of the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (The Academy) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and other ...

in 2003. He holds honorary doctorates from the

University of Waterloo The University of Waterloo (UWaterloo, UW, or Waterloo) is a Public university, public research university located in Waterloo, Ontario, Canada. The main campus is on of land adjacent to uptown Waterloo and Waterloo Park. The university also op ...

, from the

University of Helsinki The University of Helsinki (, ; UH) is a public university in Helsinki, Finland. The university was founded in Turku in 1640 as the Royal Academy of Åbo under the Swedish Empire, and moved to Helsinki in 1828 under the sponsorship of Alexander ...

, and from the

. He is a Fellow of the

American Association for the Advancement of Science The American Association for the Advancement of Science (AAAS) is a United States–based international nonprofit with the stated mission of promoting cooperation among scientists, defending scientific freedom, encouraging scientific responsib ...

ACM ACM or A.C.M. may refer to: Aviation * AGM-129 ACM, 1990–2012 USAF cruise missile * Air chief marshal * Air combat manoeuvring or dogfighting * Air cycle machine * IATA airport code for Arica Airport in Amazonas Department, Colombia Computing ...

, and

. 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 ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Public ...

. Aho, Hopcroft, and Ullman were co-recipients of the 2017

C&C Prize The NEC C&C Prize () is an award given by the NEC Corporation is a Japanese multinational information technology and electronics corporation, headquartered at the NEC Supertower in Minato, Tokyo, Japan. It provides IT and network solutions, ...

awarded by

NEC is a Japanese multinational information technology and electronics corporation, headquartered at the NEC Supertower in Minato, Tokyo, Japan. It provides IT and network solutions, including cloud computing, artificial intelligence (AI), Inte ...

Corporation. He and Ullman were named recipients of the 2020

on March 31, 2021.ACM Turing Award Honors Innovators Who Shaped the Foundations of Programming Language Compilers and Algorithms
Retrieved March 31, 2021.

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.

Books

*A. V. Aho and J. D. Ullman, ''The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing.'' Prentice Hall, 1972. *A. V. Aho (ed.) ''Currents in the Theory of Computing.'' Prentice Hall, 1973. *A. V. Aho and J. D. Ullman, ''The Theory of Parsing, Translation, and Compiling, Vol. 2, Compiling.'' Prentice-Hall, 1973. * *A. V. Aho and J. D. Ullman, ''Principles of Compiler Design.'' Addison-Wesley, 1977. *A. V. Aho, J. E. Hopcroft, J. D. Ullman, ''Data Structures and Algorithms.'' Addison-Wesley, 1983. *A. V. Aho, R. Sethi, J. D. Ullman, '' Compilers: Principles, Techniques, and Tools.'' Addison-Wesley, Reading MA 1986. *A. V. Aho, B. W. Kernighan, and P. J. Weinberger, ''The AWK Programming Language.'' Addison-Wesley, 1988. *A. V. Aho and J. D. Ullman,
Foundations of Computer Science
'' W. H. Freeman/Computer Science Press, 1992. **A. V. Aho and J. D. Ullman, ''Foundations of Computer Science, C Edition.'' W. H. Freeman, 1995. *A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, '' Compilers: Principles, Techniques, and Tools, Second Edition.'' Addison-Wesley, 2007.

References

External links

*
Alfred V Aho
at the

Digital Library {{DEFAULTSORT:Aho, Alfred 1941 births Canadian people of Finnish descent Columbia University faculty Columbia School of Engineering and Applied Science faculty 1996 fellows of the Association for Computing Machinery Fellows of the IEEE American people of Finnish descent Living people Princeton University School of Engineering and Applied Science alumni Programming language designers Scientists at Bell Labs Canadian theoretical computer scientists Turing Award laureates University of Toronto alumni People from Timmins Scientists from Ontario Fellows of the American Academy of Arts and Sciences Members of the United States National Academy of Engineering Members of the United States National Academy of Sciences Canadian textbook writers