John McCarthy's contributions to computer science and artificial intelligence are legendary. He invented Lisp, made substantial contributions to early work in timesharing and the theory of computation, and was one of the founders of artificial intelligence and knowledge representation. This article, written in honor of McCarthy's 80th birthday, presents a brief biography, an overview of the major themes of his research, and a discussion of several of his major papers.

This article presents some fundamental ideas about representing knowledge and dealing with meaning in computer representations. I will describe the issues as I currently understand them and describe how they came about, how they fit together, what problems they solve, and some of the things that the resulting framework can do. The ideas apply not just to graph-structured "node-and-link" representations, sometimes called semantic networks, but also to representations referred to variously as frames with slots, entities with relationships, objects with attributes, tables with columns, and records with fields and to the classes and variables of object-oriented data structures. I will start by describing some background experiences and thoughts that preceded the writing of my 1975 paper, "What's in a Link," which introduced many of these issues. After that, I will present some of the key ideas from that paper with a discussion of how some of those ideas have matured since then. Finally, I will describe some practical applications of these ideas in the context of knowledge access and information retrieval and will conclude with some thoughts about where I think we can go from here.

Building rules on top of ontologies is the ultimate goal of the logical layer of the Semantic Web. To this aim an ad-hoc mark-up language for this layer is currently under discussion. It is intended to follow the tradition of hybrid knowledge representation and reasoning systems such as $\mathcal{AL}$-log that integrates the description logic $\mathcal{ALC}$ and the function-free Horn clausal language \textsc{Datalog}. In this paper we consider the problem of automating the acquisition of these rules for the Semantic Web. We propose a general framework for rule induction that adopts the methodological apparatus of Inductive Logic Programming and relies on the expressive and deductive power of $\mathcal{AL}$-log. The framework is valid whatever the scope of induction (description vs. prediction) is. Yet, for illustrative purposes, we also discuss an instantiation of the framework which aims at description and turns out to be useful in Ontology Refinement. Keywords: Inductive Logic Programming, Hybrid Knowledge Representation and Reasoning Systems, Ontologies, Semantic Web. Note: To appear in Theory and Practice of Logic Programming (TPLP)

It is widely recognized today that the management of imprecision and vagueness will yield more intelligent and realistic knowledge-based applications. Description Logics (DLs) are a family of knowledge representation languages that have gained considerable attention the last decade, mainly due to their decidability and the existence of empirically high performance of reasoning algorithms. In this paper, we extend the well known fuzzy ALC DL to the fuzzy SHIN DL, which extends the fuzzy ALC DL with transitive role axioms (S), inverse roles (I), role hierarchies (H) and number restrictions (N). We illustrate why transitive role axioms are difficult to handle in the presence of fuzzy interpretations and how to handle them properly. Then we extend these results by adding role hierarchies and finally number restrictions. The main contributions of the paper are the decidability proof of the fuzzy DL languages fuzzy-SI and fuzzy-SHIN, as well as decision procedures for the knowledge base satisfiability problem of the fuzzy-SI and fuzzy-SHIN.

We describe an application of AI search and information visualization techniques to the problem of school redistricting, in which students are assigned to home schools within a county or school district. Because of the complexity of the decision-making problem, tools are needed to help end users generate, evaluate, and compare alternative school assignment plans. A key goal of our research is to aid users in finding multiple qualitatively different redistricting plans that represent different trade-offs in the decision space. We show the resulting plans using novel visualization methods that we have developed for summarizing and comparing alternative plans.

The infrastructure of modern society is controlled by software systems that are vulnerable to attacks. Many such attacks, launched by "recreational hackers" have already led to severe disruptions and significant cost. It, therefore, is critical that we find ways to protect such systems and to enable them to continue functioning even after a successful attack. This article describes AWDRAT, a prototype middleware system for providing survivability to both new and legacy applications. AWDRAT stands for architectural differencing, wrappers, diagnosis, recovery, adaptive software, and trust modeling. AWDRAT uses these techniques to gain visibility into the execution of an application system and to compare the application's actual behavior to that which is expected. In the case of a deviation, AWDRAT conducts a diagnosis that determines which computational resources are likely to have been compromised and then adds these assessments to its trust model. The trust model in turn guides the recovery process, particularly by guiding the system in its choice among functionally equivalent methods and resources.AWDRAT has been applied to and evaluated on an example application system, a graphical editor for constructing mission plans. We describe a series of experiments that were performed to test the effectiveness of AWDRAT in recognizing and recovering from simulated attacks, and we present data showing the effectiveness of AWDRAT in detecting a variety of compromises to the application system (approximately 90 percent of all simulated attacks are detected, diagnosed, and corrected). We also summarize some lessons learned from the AWDRAT experiments and suggest approaches for comprehensive application protection methods and techniques.

We are very pleased to republish here extended versions of a sample of the papers drawn from the Innovative Applications of Artificial Intelligence Conference (IAAI-06), which was held July 17-20, 2006, in Boston, Massachusetts. Three of these articles describe deployed applications and two describe emerging applications.

When Kurt Goedel layed the foundations of theoretical computer science in 1931, he also introduced essential concepts of the theory of Artificial Intelligence (AI). Although much of subsequent AI research has focused on heuristics, which still play a major role in many practical AI applications, in the new millennium AI theory has finally become a full-fledged formal science, with important optimality results for embodied agents living in unknown environments, obtained through a combination of theory a la Goedel and probability theory. Here we look back at important milestones of AI history, mention essential recent results, and speculate about what we may expect from the next 25 years, emphasizing the significance of the ongoing dramatic hardware speedups, and discussing Goedel-inspired, self-referential, self-improving universal problem solvers.

This research hypothesized that a practical approach in the form of a solution framework known as Natural Language Understanding and Reasoning for Intelligence (NaLURI), which combines full-discourse natural language understanding, powerful representation formalism capable of exploiting ontological information and reasoning approach with advanced features, will solve the following problems without compromising practicality factors: 1) restriction on the nature of question and response, and 2) limitation to scale across domains and to real-life natural language text.

Matchmaking arises when supply and demand meet in an electronic marketplace, or when agents search for a web service to perform some task, or even when recruiting agencies match curricula and job profiles. In such open environments, the objective of a matchmaking process is to discover best available offers to a given request. We address the problem of matchmaking from a knowledge representation perspective, with a formalization based on Description Logics. We devise Concept Abduction and Concept Contraction as non-monotonic inferences in Description Logics suitable for modeling matchmaking in a logical framework, and prove some related complexity results. We also present reasonable algorithms for semantic matchmaking based on the devised inferences, and prove that they obey to some commonsense properties. Finally, we report on the implementation of the proposed matchmaking framework, which has been used both as a mediator in e-marketplaces and for semantic web services discovery.