Hector Levesque and Moshe Vardi receive the ACM - AAAI Allen Newell Award.
Hector Levesque, University of Toronto, is recognized for fundamental contributions to knowledge representation and reasoning, and their broader influence within theoretical computer science, databases, robotics, and the study of Boolean satisfiability.
Levesque is recognized for his outstanding contributions to the broad core of logic-inspired artificial intelligence and the impact they have had across multiple sub-disciplines within computer science. With collaborators, he has made fundamental contributions to cognitive robotics, multi-agent systems, theoretical computer science, and database systems, as well as in philosophy and cognitive psychology. These have inspired applications such as the semantic web and automated verification. He is internationally recognized as one of the deepest and most original thinkers within AI and a researcher who has advanced the flame that AI pioneer Alan Newell lit.
On the representation side, Levesque has worked on the formalization of several concepts pertaining to artificial and natural agents including belief, goals, intentions, ability, and the interaction between knowledge, perception and action.
On the reasoning side, his research has focused on how automated reasoning can be kept computationally tractable, including the use of greedy local search methods. He is recognized for his fundamental contributions to the development of several new fields of research including the fields of description logic, the study of tractability in knowledge representation, the study of intention and teamwork, the hardness of satisfiability problems, and cognitive robotics. Levesque has also made fundamental contributions to the development of the systematic use of beliefs, desires, and intentions in the development of intelligent software, where his formalization of many aspects of intention and teamwork has shaped the entire approach to the use of these terms and the design of intelligent agents.
Moshe Vardi, Rice University, is cited for contributions to the development of logic as a unifying foundational framework and a tool for modeling computational systems.
Vardi has made major contributions to a wide variety of fields, including database theory, program verification, finite-model theory, reasoning about knowledge, and constraint satisfaction. He is perhaps the most influential researcher working at the interface of logic and computer science, building bridges between communities in computer science and beyond. With his collaborators he has made fundamental contributions to major research areas, including: 1) investigation of the logical theory of databases, where his focus on the trade-off between expressiveness and computational complexity laid the foundations for work on integrity constraints, complexity of query evaluation, incomplete information, database updates, and logic programming in databases; 2) the automata-theoretic approach to reactive systems, which laid mathematical foundations for verifying that a program meets its specifications, and 3) reasoning about knowledge through his development of epistemic logic.
In database theory, Vardi developed a theory of general data dependencies, finding axiomatizations and resolving their decision problem; introduced two basic notions of measuring the complexity of algorithms for evaluating queries, data-complexity, and query-complexity, which soon became standard in the field; created a logical theory of data updates; and characterized the expressive power of query languages and related them to complexity classes.
In software and hardware verification, Vardi introduced an automata-theoretic approach to the verification of reactive systems that revolutionized the field, using automata on infinite strings and trees to represent both the system being analyzed and undesirable computations of the system. Vardi’s automata-theoretic approach has played a central role over the last 30 years of research in the field and in the development of verification tools.
In knowledge theory, Vardi developed rigorous foundations for reasoning about the knowledge of multi-agent and distributed systems, a problem of central importance in many disciplines; his co- authored book on the subject is the definitive source for this field.
