COMBINING KNOWLEDGE BASES CONSISTING OF FIRST-ORDER THEORIES

Consider the construction of an expert system by encoding the knowledge of different experts. Suppose the knowledge provided by each expert is encoded into a knowledge base. Then the process of combining the knowledge of these different experts is an important and nontrivial problem. We study this problem here when the expert systems are considered to be first-order theories. We present techniques for resolving inconsistencies in such knowledge bases. We also provide algorithms for implementing these techniques.     

Stable and extension class theory for logic programs and default logics

The stable model semantics (cf. Gelfond and Lifschitz [1]) for logic programs suffers from the problem that programs may not always have stable models. Likewise, default theories suffer from the problem that they do not always have extensions. In such cases, both these formalisms for non-monotonic reasoning have an inadequate semantics. In this paper, we propose a novel idea-that of extension classes for default logics, and of stable classes for logic programs. It is shown that the extension class and stable class semantics extend the extension and stable model semantics respectively. This allows us to reason about inconsistent default theories, and about logic programs with inconsistent completions. Our work extends the results of Marek and Truszczynski [2] relating logic programming and default logics.     

Secure Agents

With the rapid proliferation of software agents, there comes an increased need for agents to ensure that they do not provide data and/or services to unauthorized users. We first develop an abstract definition of what it means for an agent to preserve data/action security. Most often, this requires an agent to have knowledge that is impossible to acquire – hence, we then develop approximate security checks that take into account, the fact that an agent usually has incomplete/approximate beliefs about other agents. We develop two types of security checks – static ones that can be checked prior to deploying the agent, and dynamic ones that are executed at run time. We prove that a number of these problems are undecidable, but under certain conditions, they are decidable and (our definition of) security can be guaranteed. Finally, we propose a language within which the developer of an agent can specify her security needs, and present provably correct algorithms for static/dynamic security verification.     

An Algebra for PowerPoint Sources

There are now millions of PowerPoint documents available within corporate intranets and/or over the Internet. In this paper, we develop a formal model of PowerPoint databases. We propose a relational style algebra called pptA (PowerPoint Algebra) to query PowerPoint databases. The algebra contains some new operators (such as the APPLY operator that changes properties of objects, slides and presentations) as well as interesting twists on relational operators (e.g. join and cartesian product allow different entities being joined together to share attributes whose values may be merged). We prove a set of equivalence results within this algebra. We have implemented a version of pptA—the paper provides a cost model and experimental results on the conditions under which these equivalences are useful.     

An event-based model for continuous media data on heterogeneous disk servers

Over the last few years, there has been intense work on the problem of retrieval of continuous media (CM) data from disk. However, no single unified framework exists within which such retrieval problems can be studied. In this paper, we first propose a formal model for CM data retrieval from heterogeneous disk servers. This model can be used to characterize CM data retrieval problems independently of how data is laid out on disk, and what objectives (e.g., minimize client delay, maximize buffer utilization, etc.) the system manager is interested in. We then show how using this formal model, we can neatly define what it means to optimally handle events that occur in movie-on-demand (MOD) systems. Examples of such events include new clients entering the system, old clients leaving the system, continuing clients doing pause, rewind and fast-forward operations. Multiple events may occur simultaneously and we show how such events trigger state transitions in the system. We then develop an algorithm called the QuickSOL algorithm that handles events occurring in MOD systems. This algorithm works in two phases: in the first phase, it quickly finds a way of handling as many of the events occurring at time t as possible. In the second phase, it optimizes the solution found in the first phase. The advantage is that the algorithm can be interrupted anytime after the first phase is completed. We report on experiments showing that QuickSOL works well in practice.     

Guest Editorial

Multimedia Tools and Applications -     

An algebra for creating and querying multimedia presentations

Over the last few years, there has been a tremendous increase in the number of interactive multimedia presentations prepared by different individuals and organizations. In this paper, we present an algebra for creating and querying interactive multimedia presentation databases. This algebra operates on trees whose branches reflect different possible playouts of a set of presentations. The algebra not only extends all the classical relational operators to such databases, but also introduces a variety of novel operators for combining multiple presentations. As our algebra supports merging parts or all of existing presentations, this algebra can also be used as an authoring tool for creating multimedia presentations. We prove a host of equivalence results for queries in this algebra, which may be used to build query optimizers for interactive presentation databases.     

Dualities between alternative semantics for logic programming and nonmonotonic reasoning

The Gelfond-Lifschitz operator associated with a logic program (and likewise the operator associated with default theories by Reiter) exhibits oscillating behavior. In the case of logic programs, there is always at least one finite, nonempty collection of Herbrand interpretations around which the Gelfond-Lifschitz operator bounces around. The same phenomenon occurs with default logic when Reiter's operator is considered. Based on this, a stable class semantics and extension class semantics has been proposed. The main advantage of this semantics was that it was defined for all logic programs (and default theories), and that this definition was modelled using the standard operators existing in the literature such as Reiter's operator. In this paper our primary aim is to prove that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming. In the stable class semantics, classes that were minimal with respect to Smyth's power-domain ordering were selected. We show that the well-founded semantics precisely corresponds to a class that is minimal w.r.t. Hoare's power domain ordering: the well-known dual of Smyth's ordering. Besides this elegant duality, this immediately suggests how to define a well-founded semantics for default logic in such a way that the dualities that hold for logic programming continue to hold for default theories. We show how the same technique may be applied to strong autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.     

Building Agility for Developing Agile Design Information Systems

Agile manufacturing relies heavily on the quality of information that organizations have and on their ability to organize and reuse it. Constant inflow of information and knowledge is the fuel of agile manufacturing. In the process of forming virtual enterprises, these new organizations have to be equipped with information systems that integrate their present legacy technology and improve upon it. To support the quick formation of virtual organizations, one must have the ability to develop such systems quickly. Over the past few years we have evolved, through collaborative projects with industry, an approach composed of methods and an information infrastructure called n-dim that improves the ability of becoming agile manufacturers of information systems, by responding quickly to information needs of new and evolving organizations. Following an analysis of the requirements of information systems for agile design, we discuss this approach; describe some of the infrastructure features; and present several examples of simple applications that illustrate them. We summarize by discussing the advantages and limitations of our approach.     

A Deductive Database Approach to A.I. Planning

In this paper, we show that the classical A.I. planning problem can be modelled using simple database constructs with logic-based semantics. The approach is similar to that used to model updates and nondeterminism in active database rules. We begin by showing that planning problems can be automatically converted to Datalog_1S programs with nondeterministic choice constructs, for which we provide a formal semantics using the concept of stable models. The resulting programs are characterized by a syntactic structure (XY-stratification) that makes them amenable to efficient implementation using compilation and fixpoint computation techniques developed for deductive database systems. We first develop the approach for sequential plans, and then we illustrate its flexibility and expressiveness by formalizing a model for parallel plans, where several actions can be executed simultaneously. The characterization of parallel plans as partially ordered plans allows us to develop (parallel) versions of partially ordered plans that can often be executed faster than the original partially ordered plans.