Alon Y. Levy

AIJ Journal 2000 Journal Article

Intelligent Internet systems

• Alon Y. Levy
• Daniel S. Weld

AIJ Journal 1998 Journal Article

Combining Horn rules and description logics in CARIN

• Alon Y. Levy
• Marie-Christine Rousset

We describe carin, a novel family of representation languages, that combine the expressive power of Horn rules and of description logics. We address the issue of providing sound and complete inference procedures for such languages. We identify existential entailment as a core problem in reasoning in carin, and describe an existential entailment algorithm for the ALCNR description logic. As a result, we obtain a sound and complete algorithm for reasoning in non-recursive carin ALCNR knowledge bases, and an algorithm for rule subsumption over ALCNR. We show that in general, the reasoning problem for recursive carin- ALCNR knowledge bases is undecidable, and identify the constructors of ALCNR causing the undecidability. We show two ways in which carin- ALCNR knowledge bases can be restricted while obtaining sound and complete reasoning.

AIJ Journal 1998 Journal Article

Verification of knowledge bases based on containment checking

• Alon Y. Levy
• Marie-Christine Rousset

Building complex knowledge based applications requires encoding large amounts of domain knowledge. After acquiring knowledge from domain experts, much of the effort in building a knowledge base goes into verifying that the knowledge is encoded correctly. A knowledge base is verified if it can be shown that certain constraints always hold between the inputs and the outputs. We consider the knowledge base verification problem for Horn rule knowledge bases and for three kinds of constraints: I/O consistency constraints, I/O dependency constraints, and input completeness constraints. For the first two cases, we establish tight complexity results on the problem, and show in what cases it is decidable. In the third case, we show that the problem is, in general, undecidable, and we identify two decidable cases. In our analysis we show how the properties of the problem vary depending on the presence of recursion in the Horn rules, the presence of the interpreted predicates =, ⩽, < and ≠ and the presence of negation in the antecedents of the rules. Our approach to the verification problem is based on showing a close relationship to the problem of query containment, studied in the database literature. This connection also provides novel algorithms for the knowledge base verification problem. Finally, we provide the first algorithm for verifying hybrid knowledge bases that combine the expressive power of Horn rules and the description logicALCNR.

AIJ Journal 1997 Journal Article

Automated model selection for simulation based on relevance reasoning

• Alon Y. Levy
• Yumi Iwasaki
• Richard Fikes

Constructing an appropriate model is a crucial step in performing the reasoning required to successfully answer a query about the behavior of a physical situation. In the compositional modeling approach of Falkenhainer and Forbus (1991), a system is provided with a library of composable pieces of knowledge about the physical world called model fragments. The model construction problem involves selecting appropriate model fragments to describe the situation. Model construction can be considered either for static analysis of a single state or for simulation of dynamic behavior over a sequence of states. The latter is significantly more difficult than the former since one must select model fragments without knowing exactly what will happen in the future states. The model construction problem in general can advantageously be formulated as a problem of reasoning about relevance of knowledge that is available to the system using a general framework for reasoning about relevance described by Levy (1993) and Levy and Sagiv (1993). In this paper, we present a model formulation procedure based on that framework for selecting model fragments efficiently for the case of simulation. For such an algorithm to be useful, the generated model must be adequate for answering the given query and, at the same time, as simple as possible. We define formally the concepts of adequacy and simplicity and show that the algorithm in fact generates an adequate and simplest model.

AIJ Journal 1997 Journal Article

Speeding up inferences using relevance reasoning: a formalism and algorithms

• Alon Y. Levy
• Richard E. Fikes
• Yehoshua Sagiv

Irrelevance reasoning refers to the process in which a system reasons about which parts of its knowledge are relevant (or irrelevant) to a specific query. Aside from its importance in speeding up inferences from large knowledge bases, relevance reasoning is crucial in advanced applications such as modeling complex physical devices and information gathering in distributed heterogeneous systems. This article presents a novel framework for studying the various kinds of irrelevance that arise in inference and efficient algorithms for relevance reasoning. We present a proof-theoretic framework for analyzing definitions of irrelevance. The framework makes the necessary distinctions between different notions of irrelevance that are important when using them for speeding up inferences. We describe the query-tree algorithm which is a sound, complete and efficient algorithm for automatically deriving certain kinds of irrelevance claims for Horn-rule knowledge bases and several extensions. Finally, we describe experimental results that show that significant speedups (often orders of magnitude) are obtained by employing the query-tree in inference.

ECAI Conference 1996 Conference Paper

CARIN: A Representation Language Combining Horn Rules and Description Logics

• Alon Y. Levy
• Marie-Christine Rousset

AAAI Conference 1996 Conference Paper

Query-Answering Algorithms for Information Agents

• Alon Y. Levy

We describe the architecture and queryanswering algorithms used in the Information Manifold, an implemented information gathering system that provides uniform access to structured information sources on the World-Wide Web. Our architecture provides an expressive language for describing information sources, which makes it easy to add new sources and to model the fine-grained distinctions between their contents. The queryanswering algorithm guarantees that the descriptions of the sources are exploited to access only sources that are relevant to a given query. Accessing only relevant sources is crucial to scale up such a system to large numbers of sources. In addition, our algorithm can exploit run-time information to further prune information sources and to reduce the cost of query planning.

AAAI Conference 1996 Conference Paper

The Limits on Combining Recursive Horn Rules with Description Logics

• Alon Y. Levy

Horn rule languages have formed the basis for many Artificial Intelligence application languages, but are not expressive enough to model domains with a rich hierarchical structure. Description logics have been designed especially to model rich hierarchies. Several applications would significantly benefit from combining the expressive power of both formalisms. This paper focuses on combining recursive function-free Horn rules with the expressive description logic &, Chf’ R, and shows exactly when a hybrid language with decidable inference can be obtained. First, we show that several of the core constructors of description logics lead by themselves to undecidability of inference when combined with recursive function-free Horn rules. We then show that without these constructors we obtain a maximal subset of &CN7E that yields a decidable hybrid language. Finally, we describe a restriction on the Horn rules that guarantees decidable inference when combined with all of &Cn/Z, and covers many of the common usages of recursive rules.

AAAI Conference 1996 Conference Paper

Verification of Knowledge Bases Based on Containment Checking

• Alon Y. Levy

Building complex knowledge based applications requires encoding large amounts of domain knowledge. After acquiring knowledge from domain experts, much of the effort in building a knowledge base goes into verifying that the knowledge is encoded correctly. We consider the problem of verifying hybrid knowledge bases that contain both Horn rules and a terminology in a description logic. Our approach to the verification problem is based on showing a close relationship to the problem of query containment. Our first contribution, based on this relationship, is presenting a thorough analysis of the decidability and complexity of the verification problem, for knowledge bases containing recursive rules and the interpreted predicates =, 5, < and f. Second, we show that important new classes of constraints on correct inputs and outputs can be expressed in a hybrid setting, in which a description logic class hierarchy is also considered, and we present the first complete algorithm for verifying such hybrid knowledge bases.

AAAI Conference 1994 Conference Paper

Creating Abstractions Using Relevance Reasoning

• Alon Y. Levy

Reasoning with multiple levels of abstraction is a powerful method of controlling problem solving in complex domains. We consider the problem of simplifying a knowledge base by creating an abstraction that is tailored for a given set of queries. Our approach is based on associating formally an abstraction with some irrelevant detail that is removed from the knowledge base. We show how creating an abstraction and determining its utility amounts to automatically deciding which aspects of a representation are irrelevant to a query. As a result, we derive a general algorithm schema for automatically generating abstractions for a query. As an instance of the schema, we describe a novel algorithm for automatically abstracting a KB by projecting out relation arguments.

IJCAI Conference 1993 Conference Paper

Exploiting Irrelevance Reasoning to Guide Problem Solving

• Alon Y. Levy
• Yehoshua Sagiv