Alfred Aho
Encyclopedia
Alfred Vaino Aho is a Canadian computer scientist
.
and a Ph.D. in Electrical Engineering/Computer Science from Princeton University
. 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. he holds the Lawrence Gussman Chair of Computer Science
at Columbia University
. 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
s and the nested stack automaton
as vehicles for extending the power of context-free languages but retaining many of their decidability and closure properties. Indexed grammars have been used to model 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 and string pattern matching algorithms which he implemented in the first versions of the Unix
tools
and is widely used in a number of bibliographic search systems, including the one developed by Margaret J. Corasick, and other string searching applications.
At Bell Labs, Aho worked closely with Steve Johnson and Jeffrey Ullman
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
, and Michael E. Lesk and Eric E. Schmidt
used Aho's regular expression pattern matching algorithms to create the lexical-analyzer generator lex. 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
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 2007 also by Monica Lam to create "the purple dragon book." The dragon books have been the most widely used compiler textbooks throughout the world.
In 1974, Aho, John Hopcroft
, 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 structures 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
and Brian Kernighan
(the 'A' stands for "Aho").
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.
Aho has received many prestigious honors, including the IEEE
's John von Neumann Medal
and membership in the National Academy of Engineering
. He was elected a Fellow of the American Academy of Arts and Sciences
in 2003. He holds honorary doctorates from the University of Waterloo
in Ontario and from the University of Helsinki
in Finland
, and is a Fellow of the American Association for the Advancement of Science
, ACM
, Bell Labs
, and IEEE. He won the Great Teacher Award from the Society of Columbia Graduates in 2003.
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.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
.
Career
Aho received a B.A.Sc. in Engineering Physics from the University of TorontoUniversity of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
and a Ph.D. in Electrical Engineering/Computer Science from Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
. He conducted research at Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
from 1967 to 1991, and again from 1997 to 2002 as Vice President of the Computing Sciences Research Center. he holds the Lawrence Gussman Chair of Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at Columbia University
Columbia University
Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...
. 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 grammar
An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals, as well as index symbols, which appear only in intermediate derivation steps on a stack associated with the non-terminals of that step.The...
s and the nested stack automaton
Nested stack automaton
In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks. A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an indexed language....
as vehicles for extending the power of context-free languages but retaining many of their decidability and closure properties. Indexed grammars have been used to model 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 and string pattern matching algorithms which he implemented in the first versions of the Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
tools
egrep and fgrep. The fgrep algorithm has become known as the Aho-Corasick algorithmAho-Corasick algorithm
The Aho–Corasick string matching algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings within an input text. It matches all patterns simultaneously...
and is widely used in a number of bibliographic search systems, including the one developed by Margaret J. Corasick, and other string searching applications.
At Bell Labs, Aho worked closely with Steve Johnson and Jeffrey Ullman
Jeffrey Ullman
Jeffrey David Ullman is a renowned computer scientist. His textbooks on compilers , theory of computation , data structures, and databases are regarded as standards in their fields.-Early life & Career:Ullman received a Bachelor of Science degree in Engineering...
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
The computer program yacc is a parser generator developed by Stephen C. Johnson at AT&T for the Unix operating system. The name is an acronym for "Yet Another Compiler Compiler." It generates a parser based on an analytic grammar written in a notation similar to BNF.Yacc used to be available as...
, and Michael E. Lesk and Eric E. Schmidt
Eric E. Schmidt
Eric Emerson Schmidt is an American software engineer and the current executive chairman of Google. From 2001 to 2011, he served as the chief executive officer of Google....
used Aho's regular expression pattern matching algorithms to create the lexical-analyzer generator lex. 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
Principles of Compiler Design, by Alfred Aho and Jeffrey D. Ullman, is a classic textbook on compilers for computer programming languages.It is often called the "dragon book" and its cover depicts a knight and a dragon in battle; the dragon is green, and labelled "Complexity of Compiler...
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
Ravi Sethi is an Indian computer scientist retired from Bell Labs and president of Avaya Labs Research. He is best known as one of three authors of the classic computer science textbook Compilers: Principles, Techniques, and Tools, also known as the Dragon Book.Sethi was born in 1947 in Murdana,...
to create a new edition, "the red dragon book" (which was briefly shown in the 1995 movie "Hackers"), and in 2007 also by Monica Lam to create "the purple dragon book." The dragon books have been the most widely used compiler textbooks throughout the world.
In 1974, Aho, John Hopcroft
John Hopcroft
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 the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
, 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 structures 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 J. Weinberger
Peter Jay Weinberger 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...
and Brian Kernighan
Brian Kernighan
Brian Wilson Kernighan is a Canadian computer scientist who worked at Bell Labs alongside Unix creators Ken Thompson and Dennis Ritchie and contributed to the development of Unix. He is also coauthor of the AWK and AMPL programming languages. The 'K' of K&R C and the 'K' in AWK both stand for...
(the 'A' stands for "Aho").
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.
Aho has received many prestigious honors, including the IEEE
Institute of Electrical and Electronics Engineers
The Institute of Electrical and Electronics Engineers is a non-profit professional association headquartered in New York City that is dedicated to advancing technological innovation and excellence...
's John von Neumann Medal
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 entrepreneurial, and need not have been made...
and membership in the National Academy of Engineering
National Academy of Engineering
The National Academy of Engineering is a government-created non-profit institution in the United States, that was founded in 1964 under the same congressional act that led to the founding of the National Academy of Sciences...
. He was elected a Fellow of the American Academy of Arts and Sciences
American Academy of Arts and Sciences
The American Academy of Arts and Sciences is an independent policy research center that conducts multidisciplinary studies of complex and emerging problems. The Academy’s elected members are leaders in the academic disciplines, the arts, business, and public affairs.James Bowdoin, John Adams, and...
in 2003. He holds honorary doctorates from the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
in Ontario and from the University of Helsinki
University of Helsinki
The University of Helsinki is a university located in Helsinki, Finland since 1829, but was founded in the city of Turku in 1640 as The Royal Academy of Turku, at that time part of the Swedish Empire. It is the oldest and largest university in Finland with the widest range of disciplines available...
in Finland
Finland
Finland , officially the Republic of Finland, is a Nordic country situated in the Fennoscandian region of Northern Europe. It is bordered by Sweden in the west, Norway in the north and Russia in the east, while Estonia lies to its south across the Gulf of Finland.Around 5.4 million people reside...
, and is a Fellow of the American Association for the Advancement of Science
American Association for the Advancement of Science
The American Association for the Advancement of Science is an international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific responsibility, and supporting scientific education and science outreach for the...
, ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
, Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
, and IEEE. He won the Great Teacher Award from the Society of Columbia Graduates in 2003.
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.
Teaching
Professor Alfred Aho has taught at Columbia University in New York 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. ISBN 0-13-914556-7
- 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. ISBN 978-0-13-914564-3
- A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN 0-201-00023-7
- A. V. Aho and J. D. Ullman, Principles of Compiler Design. Addison-Wesley, 1977. ISBN 0-201-00022-9
- A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms. Addison-Wesley, 1983. ISBN 0-201-00023-7
- A. V. Aho, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and ToolsCompilers: Principles, Techniques, and ToolsCompilers: Principles, Techniques, and Tools is a famous computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction...
. Addison-Wesley, Reading MA 1986. ISBN 0-201-10088-6 - A. V. Aho, B. W. Kernighan, and P. J. Weinberger, The AWK Programming Language. Addison-Wesley, 1988. ISBN 978-0-201-07981-4
- 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. ISBN 978-0-7167-8284-1
- A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and ToolsCompilers: Principles, Techniques, and ToolsCompilers: Principles, Techniques, and Tools is a famous computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman about compiler construction...
, Second Edition. Addison-Wesley, 2007. ISBN 978-0-321-48681-3