Die vorliegende Arbeit untersucht das sogenannte logische Allwissenheitsproblem' (Logical Omniscience Problem) der epistemischen Logik und schlägt einen neuen Ansatz zur Lösung des Problems vor. Die epistemische Logik, die ursprünglich als eine Teildisziplin der philosophischen Logik entwickelt wurde, findet heute Anwendung in so unterschiedlichen Gebieten wie Philosophie, Sprachwissenschaft, Wirtschaftswissenschaft und Informatik. In der Informatik und der Künstlichen Intelligenz ist die epistemische Logik einer der Hauptformalismen zur Wissensrepräsentation und zur Spezifikation von Multiagentensystemen geworden. Allerdings ist es eine sehr umstrittene Frage, ob die epistemische Logik für diese Anwendungen geeignet ist. Kritiker behaupten, daß die epistemische Logik die Begriffe des Wissens und des Glaubens nicht adäquat erfassen kann und folglich für die Repräsentation von Wissen ungeeignet ist. Ihre Behauptung gründet sich auf der Tatsache, daß die meisten Systeme der epistemischen Logik sehr starke Idealisierungen hinsichtlich der logischen Fähigkeiten der epistemischen Subjekte (englisch: agents) machen. Es wird z. B. angenommen, daß die epistemischen Subjekte alle logischen Wahrheiten kennen, oder daß sie alle logischen Konsequenzen einer Aussage kennen, wenn sie diese Aussage glauben. Dieses Problem is als das logische Allwissenheitsproblem' (Logical Omniscience Problem) bekannt. Es gibt in der Literatur eine Reihe von Ansätzen, dieses Problem zu lösen. Fast alle vorgeschlagenen Lösungen verfolgen die Strategie, schwächere modale Systeme zu betrachten. Ich werde zeigen, daß diese Lösungen unbefriedigend sind: in dieser Weise kann logische Allwissenheit vermieden werden, aber viele Intuitionen über die Begriffe Glauben und Wissen gehen verloren. Also können auch die schwächeren epistemischen Systeme die genannten Begriffe nicht adäquat erfassen. Ein anderer Lösungsansatz wird vorgeschlagen. Ich werde argumentieren, daß sich die Hauptprobleme der epistemischen Logik in einem statischen Rahmen nicht lösen lassen. Um diese Probleme zu lösen, müssen wir auch die Denkaktivitäten der epistemischen Subjekte in Betracht ziehen. Zur Modellierung von Wissen (und Glauben) brauchen wir eine dynamische epistemische Logik. Ich werde zeigen, daß Axiome der epistemischen Logik die folgende Form haben muß: wenn alle Prämissen einer gültigen Schlußregel gewußt (geglaubt) werden und wenn das Subjekt die notwendige Folgerung vollzieht, dann weißt (glaubt) es auch die Konklusion. Um diese Idee zu formalisieren, schlage ich vor, die epistemische Logik zu d.h., eine dynamische Komponente in die Sprache einzuführen. An einem Beispiel wird erläutert, wie die Dynamisierung' der epistemischen Logik realisiert werden kann.

We discuss a new concept of agent programs that combines logic programming with reasoning about actions. These agent logic programs are characterized by a clear separation between the specification of the agent’s strategic behavior and the underlying theory about the agent’s actions and their effects. This makes it a generic, declarative agent programming language, which can be combined with an action representation formalism of one’s choice. We present a declarative semantics for agent logic programs along with (two versions of) a sound and complete operational semantics, which combines the standard inference mechanisms for (constraint) logic programs with reasoning about actions.

We provide a systematic in-depth study of the semantics of abstract dialectical frameworks (ADFs), a recent generalisation of Dung\''s abstract argumentation frameworks. This is done by associating with an ADF its characteristic one-step consequence operator and defining various semantics for ADFs as different fixpoints of this operator. We first show that several existing semantical notions are faithfully captured by our definition, then proceed to define new ADF semantics and show that they are proper generalisations of existing argumentation semantics from the literature. Most remarkably, this operator-based approach allows us to compare ADFs to related nonmonotonic formalisms like Dung argumentation frameworks and propositional logic programs. We use polynomial, faithful and modular translations to relate the formalisms, and our results show that both abstract argumentation frameworks and abstract dialectical frameworks are at most as expressive as propositional normal logic programs.

Abstract dialectical frameworks (ADFs) have recently been proposed as a versatile generalization of Dung''s abstract argumentation frameworks (AFs). In this paper, we present a comprehensive analysis of the computational complexity of ADFs. Our results show that while ADFs are one level up in the polynomial hierarchy compared to AFs, there is a useful subclass of ADFs which is as complex as AFs while arguably offering more modeling capacities. As a technical vehicle, we employ the approximation fixpoint theory of Denecker, Marek and Truszczyński, thus showing that it is also a useful tool for complexity analysis of operator-based semantics.

Description logics (DL) knowledge bases are often build by users with expertise in the application domain, but little expertise in logic. To support this kind of users when building their knowledge bases a number of extension methods have been proposed to provide the user with concept descriptions as a starting point for new concept definitions. The inference service central to several of these approaches is the computation of (least) common subsumers of concept descriptions. In case disjunction of concepts can be expressed in the DL under consideration, the least common subsumer (lcs) is just the disjunction of the input concepts. Such a trivial lcs is of little use as a starting point for a new concept definition to be edited by the user. To address this problem we propose two approaches to obtain "meaningful" common subsumers in the presence of disjunction tailored to two different methods to extend DL knowledge bases. More precisely, we devise computation methods for the approximation-based approach and the customization of DL knowledge bases, extend these methods to DLs with number restrictions and discuss their efficient implementation.

Die Transformation der Industriegesellschaft zur „Wissensgesellschaft“ ist ein in vielen Punk-ten erst noch zu verstehender und zu erforschender Prozess. Man muss sich nicht lange mit der scholastischen Frage aufhalten, ob man aktuelle Umbrüche in Erwerbsarbeit und Gesell-schaft unter diesem Label angemessen zusammenfassen kann, solange man den Begriff als eine unter verschiedenen möglichen „Brillen“ betrachtet, die die Aufmerksamkeit auf be-stimmte Trends lenkt und die Annahmen bezüglich ihrer inneren Zusammenhänge klar formu-liert.

Das Anliegen der Arbeit besteht in der Entwicklung eines Wissensrepräsentationsmodells, das sich insbesondere für die Beschreibung komplex strukturierter Objekte eignet. Den Ausgangspunkt bildet eine Charakterisierung der Problematik der Wissensrepräsentation. Aus der Darstellung eines für das Gebiet der rechnergestützten Konstruktion typischen Diskursbereiches Getriebekonstruktion lassen sich Anforderungen an Modelle zur Beschreibung komplex strukturierter Objekte in Wissensbasen ableiten. Der Hauptteil der Arbeit besteht in der Entwicklung eines funktionalen Wissensrepräsentationsmodells, das diesen Anforderungen gerecht wird. Das Modell ermöglicht gleichzeitig eine effiziente Implementation wissensbasierter Systeme auf der Grundlage der Programmiersprache LISP sowie das Herstellen von Beziehungen zu Datenmodellen einerseits und Wissensrepräsentationsmodellen, insbesondere der Prädikatenlogik erster Ordnung, andererseits. Unter Bezugnahme auf die Datenbanktechnologie wird die Struktur von Wissensbanksystemen beschrieben. Ein wesentlicher Aspekt der Arbeit besteht im Aufzeigen der Möglichkeit und des Weges, das Wissen eines Konstrukteurs zu formalisieren und in eine Wissensbasis abzubilden.:1. Einleitung 2. Wissensrepräsentation in technischen Systemen 3. Beispielsdiskursbereiche 4. Funktionales Wissensrepräsentationsmodell 5. Beziehungen zwischen Prädikatenlogik erster Ordnung und funktionalem Wissensrepräsentationsmodell 6. Aufbau von Wissensbanksystemen 7. Anwendung des funktionalen Wissensrepräsentationsmodells für die Implementation wissensbasierter Systeme 8. Schlussbemerkungen

Knowledge Space Theory (KST) links in several ways to Formal Concept Analysis (FCA). Recently, the probabilistic and statistical aspects of KST have been further developed by several authors. We review part of the recent results, and describe some of the open problems. The question of whether the outcomes can be useful in FCA remains to be investigated.

Answer Set Programming (ASP) is an emerging paradigm for declarative programming, in which a computational problem is specified by a logic program such that particular models, called answer sets, match solutions. ASP faces a growing range of applications, demanding for high-performance tools able to solve complex problems. ASP integrates ideas from a variety of neighboring fields. In particular, automated techniques to search for answer sets are inspired by Boolean Satisfiability (SAT) solving approaches. While the latter have firm proof-theoretic foundations, ASP lacks formal frameworks for characterizing and comparing solving methods. Furthermore, sophisticated search patterns of modern SAT solvers, successfully applied in areas like, e.g., model checking and verification, are not yet established in ASP solving. We address these deficiencies by, for one, providing proof-theoretic frameworks that allow for characterizing, comparing, and analyzing approaches to answer set computation. For another, we devise modern ASP solving algorithms that integrate and extend state-of-the-art techniques for Boolean constraint solving. We thus contribute to the understanding of existing ASP solving approaches and their interconnections as well as to their enhancement by incorporating sophisticated search patterns. The central idea of our approach is to identify atomic as well as composite constituents of a propositional logic program with Boolean variables. This enables us to describe fundamental inference steps, and to selectively combine them in proof-theoretic characterizations of various ASP solving methods. In particular, we show that different concepts of case analyses applied by existing ASP solvers implicate mutual exponential separations regarding their best-case complexities. We also develop a generic proof-theoretic framework amenable to language extensions, and we point out that exponential separations can likewise be obtained due to case analyses on them. We further exploit fundamental inference steps to derive Boolean constraints characterizing answer sets. They enable the conception of ASP solving algorithms including search patterns of modern SAT solvers, while also allowing for direct technology transfers between the areas of ASP and SAT solving. Beyond the search for one answer set of a logic program, we address the enumeration of answer sets and their projections to a subvocabulary, respectively. The algorithms we develop enable repetition-free enumeration in polynomial space without being intrusive, i.e., they do not necessitate any modifications of computations before an answer set is found. Our approach to ASP solving is implemented in clasp, a state-of-the-art Boolean constraint solver that has successfully participated in recent solver competitions. Although we do here not address the implementation techniques of clasp or all of its features, we present the principles of its success in the context of ASP solving. / Antwortmengenprogrammierung (engl. Answer Set Programming; ASP) ist ein Paradigma zum deklarativen Problemlösen, wobei Problemstellungen durch logische Programme beschrieben werden, sodass bestimmte Modelle, Antwortmengen genannt, zu Lösungen korrespondieren. Die zunehmenden praktischen Anwendungen von ASP verlangen nach performanten Werkzeugen zum Lösen komplexer Problemstellungen. ASP integriert diverse Konzepte aus verwandten Bereichen. Insbesondere sind automatisierte Techniken für die Suche nach Antwortmengen durch Verfahren zum Lösen des aussagenlogischen Erfüllbarkeitsproblems (engl. Boolean Satisfiability; SAT) inspiriert. Letztere beruhen auf soliden beweistheoretischen Grundlagen, wohingegen es für ASP kaum formale Systeme gibt, um Lösungsmethoden einheitlich zu beschreiben und miteinander zu vergleichen. Weiterhin basiert der Erfolg moderner Verfahren zum Lösen von SAT entscheidend auf fortgeschrittenen Suchtechniken, die in gängigen Methoden zur Antwortmengenberechnung nicht etabliert sind. Diese Arbeit entwickelt beweistheoretische Grundlagen und fortgeschrittene Suchtechniken im Kontext der Antwortmengenberechnung. Unsere formalen Beweissysteme ermöglichen die Charakterisierung, den Vergleich und die Analyse vorhandener Lösungsmethoden für ASP. Außerdem entwerfen wir moderne Verfahren zum Lösen von ASP, die fortgeschrittene Suchtechniken aus dem SAT-Bereich integrieren und erweitern. Damit trägt diese Arbeit sowohl zum tieferen Verständnis von Lösungsmethoden für ASP und ihrer Beziehungen untereinander als auch zu ihrer Verbesserung durch die Erschließung fortgeschrittener Suchtechniken bei. Die zentrale Idee unseres Ansatzes besteht darin, Atome und komposite Konstrukte innerhalb von logischen Programmen gleichermaßen mit aussagenlogischen Variablen zu assoziieren. Dies ermöglicht die Isolierung fundamentaler Inferenzschritte, die wir in formalen Charakterisierungen von Lösungsmethoden für ASP selektiv miteinander kombinieren können. Darauf aufbauend zeigen wir, dass unterschiedliche Einschränkungen von Fallunterscheidungen zwangsläufig zu exponentiellen Effizienzunterschieden zwischen den charakterisierten Methoden führen. Wir generalisieren unseren beweistheoretischen Ansatz auf logische Programme mit erweiterten Sprachkonstrukten und weisen analytisch nach, dass das Treffen bzw. Unterlassen von Fallunterscheidungen auf solchen Konstrukten ebenfalls exponentielle Effizienzunterschiede bedingen kann. Die zuvor beschriebenen fundamentalen Inferenzschritte nutzen wir zur Extraktion inhärenter Bedingungen, denen Antwortmengen genügen müssen. Damit schaffen wir eine Grundlage für den Entwurf moderner Lösungsmethoden für ASP, die fortgeschrittene, ursprünglich für SAT konzipierte, Suchtechniken mit einschließen und darüber hinaus einen transparenten Technologietransfer zwischen Verfahren zum Lösen von ASP und SAT erlauben. Neben der Suche nach einer Antwortmenge behandeln wir ihre Aufzählung, sowohl für gesamte Antwortmengen als auch für Projektionen auf ein Subvokabular. Hierfür entwickeln wir neuartige Methoden, die wiederholungsfreies Aufzählen in polynomiellem Platz ermöglichen, ohne die Suche zu beeinflussen und ggf. zu behindern, bevor Antwortmengen berechnet wurden.

We discuss a new concept of agent programs that combines logic programming with reasoning about actions. These agent logic programs are characterized by a clear separation between the specification of the agent’s strategic behavior and the underlying theory about the agent’s actions and their effects. This makes it a generic, declarative agent programming language, which can be combined with an action representation formalism of one’s choice. We present a declarative semantics for agent logic programs along with (two versions of) a sound and complete operational semantics, which combines the standard inference mechanisms for (constraint) logic programs with reasoning about actions.