Kolloquium/Ringvorlesung des Graduiertenkolleg Wissensrepräsentation

Defaults can be described as knowledge items whose validity is conditioned on the absence of contradicting evidence, that is, the absence of conflicts with other defaults. When such a conflict occurs, an arbitration is in order.

A natural way of resolving conflicts is by blocking the defaults of least _reliability_ in the conflict set. As simple as this intuition may seem, its realization is faced with various difficulties, including the interference of the common consistency proviso in default rules and the intricate meaning of reliability for disjunctive defaults.

In this talk we will discuss these and further aspects of the problem, devise principles we consider essential for an adequate solution, and use them to incorporate reliability factors into a disjunctive version of Reiter's default logic.

Description Logics (DLs) are a family of knowledge representation formalisms designed for representing and reasoning about the terminological knowledge of an application domain. It turned out that DLs are well-suited for providing a logical basis for Semantic Web ontology languages. In the last decade, a lot of work was devoted to finding a good compromise between the expressive power of a DL and its computational complexity. One result of this work was the successful DL SHIQ which combines high expressive power with surprisingly good behaviour in many realistic applications.

In this talk, I will introduce Semantic Web ontology languages, their relationship with DLs, and how DL reasoners can be used to support ontology engineering. Moreover, I will talk briefly about finite model reasoning in DLs.

Our talk consists of 2 parts. In the first part we present an "agent monitoring" approach, which aims at refuting from (possibly incomplete) information at hand that a multi-agent system (\MAS) is implemented properly. In this approach, agent collaboration is abstractly described in an action theory. Action sequences reaching the collaboration goal are determined by a planner, whose compliance with the actual \MAS behavior allows to detect possible collaboration failures. The approach can be fruitfully applied to aid offline testing of a \MAS implementation, as well as online monitoring.

In the second part we investigate a formalism for solving planning problems based on "ordered task decomposition" using Answer Set Programming (\ASP). Our planning methodology is an adaptation of Hierarchical Task Network (\HTN) planning, a approach that has led recently to very some efficient planners (e.g., \SHOP).

The \ASP paradigm evolved out of the stable semantics for logic programs in recent years and is strongly related to nonmonotonic logics. It also led to various very efficient implementations (\smodels, \DLV). While all approaches of using \ASP for planning considered so far rely on action-based planning, we consider for the first time a formulation of \HTN planning as described in the \SHOP planning system and define a systematic translation method from \SHOP's representation of the planning problem into logic programs with negation. We show that our translation is sound and complete: answer sets of the logic program obtained by our translation correspond exactly to the solutions of the planning problem. Our approach does not rely on a particular system for computing answer sets and serves several purposes.

(1) It constitutes a means to evaluate \ASP systems by using well-established benchmarks from the planning community.

(2) It makes the more expressive \HTN planning available in \ASP.

(3) When our approach is implemented on \ASP solvers, its time requirement appears to grow no faster than roughly proportional to that of a dedicated \HTN planning system (\SHOP).

(4) It outperforms action-based planning methods formulated in \ASP.

(5) It sheds light on the performance of \ASP systems using different grounding strategies.

We provide a formal study of belief retraction operators that do not necessarily satisfy the (Inclusion) postulate, i.e., operators - for which K - A is not necessarily a subset of K (where K is the prior belief set and A the sentence to be retracted). Our intuition is that a rational description of belief change must do justice to cases in which dropping a belief can lead to the inclusion, or "liberation", of others. We provide two models of liberation via retraction operators, sigma-liberation and linear liberation. We show that the class of sigma-liberation operators is included in the class of linear ones and provide axiomatic characterisations for each class. We also show how any given retraction operator (including the liberation operators) can be "converted" into either a withdrawal operator (i.e., an operator satisfying (Inclusion)) or a belief revision operator via (a slight variant of) the Harper Identity and the Levi Identity respectively. (This is joint work with Samir Chopra, Aditya Ghose and Thomas Meyer.)

As soon as decision making is concerned, one has to represent the preferences of the agent (either a utility function or an ordering relation) over the set of feasible alternatives. Now, in many real-world domains, the set of alternatives is the set of assignments of a value to each of a given set of variables: in such cases, the alternatives are exponentially many and it is not reasonable to ask agents to report their preference in an explicit way. For this reason, AI researchers have developed languages for preference representation aiming at enabling a succinct representation of the description of the problem. Such preference representation languages are often built up on propositional logic. In this talk I will review different logical languages for representation and I will give some computational complexity results for the problems of comparing alternatives or selecting a nondominated alternative.

Usual ontologies are based on logical definitions or are specified by terminological relations between concepts like subtype-supertype or part-whole. We explore prototype-based ontologies, whose categories are distinguished by typical instances or prototypes. A collection of flowers, for instance, defines a flower category. We establish a link to text clustering algorithms which cluster descriptions of concepts. The we discuss how these approaches may be used to generate ontologies from text collections in an automatic way.

The information available electronically is growing rapidly. However, most of this information is contained in some unstructured documents like internet pages or emails. Special programs, so-called wrappers, are necessary to access the data contained in such documents. Usually, these wrappers are hand-crafted. In contrast, over the last years, a few approaches were developed to create such wrappers automatically by learning techniques.

In this talk we will discuss a certain technology of learning wrappers based on grammatical inference. A special language, so-called advanced elementary formal systems, AEFS for short, was developed to represent wrappers. Here, from a certain viewpoint, wrappers can be understood as special formal languages. We investigate under which circustances AEFS in general as well as special wrapper classes can be learned by computers.

This paper proposes an algorithm for causality inference based on a set of lexical knowledge bases that contain information about such items as event role, is-a hierarchy, relevant relation, antonymy, and other features. These lexical knowledge bases have mainly made use of lexical features and symbols in HowNet. Several types of questions are experimented to test the effectiveness of the algorithm here proposed. In particular, questions of the form ¡°why¡± is treated in this paper to show how causality inference works.

The concept of an institution, introduced by Goguen und Burstall, formalizes the informal notion of "logical system". Every institution consists of a collection of signatures, providing the vocabulary for constructing sentences, and for every signature there are collections of sentences and of models together with a satisfaction relation between them.

Since the truth of a sentence in logic should be essentially independent of the symbols chosen to represent its functions and relations, the satisfaction relation must be consistent with the translation of sentences and models: "Truth is invariant under change of notation".

There is a rich body of results for general institutions. Examples include general conditions under which logical structures can be composed from smaller ones, or when one can use a theorem prover of one logical system for another one. Institutions provide a foundation for approaching problems like these not only in logic, but also in programming, specification, and many other areas.

After an introduction into the field, we will show that also non-classical probabilistic and conditional logics can be viewed as institutions. Thus, not only the general results for institutions are immediately available, but also the relationships between the various logics can be stated very precisely in this framework.

Traditional theories of concept cannot answer some worrisome questions. To answer them we need such a logical theory that makes it possible to distinguish objects from the way they have been constructed. Therefore, we apply Tichý´s transparent intensional logic (TIL) where a realistic (vs. nominalistic) theory of constructions has been built up. The ontology of TIL is determined as an infinite hierarchy of entities (ramified hierarchy of types). Concepts are then defined as being closed constructions, i.e., complex objects in the algorithmic (i.e., not mereological) sense. A partial ordering of concepts is then possible; such a useful ordering is not based simply on the relation being contained in, but on the notion of requisite (of an intension).

Research in ontology has become increasingly widespread and important in the field of information system sciences. After sketching my understanding on ontology (which essentially means (a) which information is ontological (as opposed to linguistic information, logical information, etc), and (b) the main architecture of the top-level), I shall present in some details the idea of level of reality and the levels' general architecture.

Donald Nute invented a non-monotonic logic called Defeasible Logic. Plausible Logic takes Defeasible Logic as its starting point and then modifies it so that the result is arguably more powerful, more intuitive, and as efficient.

      Both Defeasible Logic and Plausible Logic were design to be implemented efficiently. However the detection of loops is necessary for any implementation, but not necessary a logic designed for human use. Decisive Plausible Logic builds detection of loops right into the logic.

      The talk will give a very brief history of Plausible Logic, an overview of the main features of Decisive Plausible Logic (DPL), an example of its use, some details of the insides of DPL, some properties of DPL, and some future planned developments.