Complexity of argumentation

Abstract

Die abstrakte Argumentation ist ein Versuch, den Prozess der menschlichen Argumentation zu formalisieren. Die Menschen verwenden Argumentation im täglichen Leben sowohl für das Argumentieren über Kenntnisse und Ansichten als auch für den Informationsaustausch. Diese Technik lässt sich auch für das Lösen zahlreicher Probleme verwenden: im Bereich der künstlichen Intelligenz aber auch in anderen Bereichen wie der Dialogspieltheorie.<br />Außerdem kann sie auch als Werkzeug für das Vergleichen von verschiedenen nicht-monotonen Logiken eingesetzt werden.<br />Die Argumentationstheorie versucht unterschiedliche Fragen zu beantworten. Dabei beschäftigt sie sich mit der Zulässigkeit eines einzelnen Arguments unter Berücksichtigung der restlichen Argumente, mit der Identifikation von gemeinsam akzeptierbaren Argumenten und mit der Entdeckung von Beziehungen und Verbindungen zwischen Eigenschaften von solchen gemeinsam akzeptierbaren Argumenten.<br />Außerdem spielen Komplexitätsanalysen eine wichtige Rolle in der Argumentationstheorie. Für die meisten algorithmischen Probleme in diesem Bereich sind keine effizienten Rechenverfahren bekannt. Daher ist auch die Suche nach geeigneten Generalisierungen und Einschränkungen von Argumentationsrahmen zu einem wichtigen Teil der Argumentationstheorie geworden.<br />Diese Diplomarbeit präsentiert eine einheitliche Darstellung der wichtigsten Komplexitätsresultate der Argumentationstheorie unter Verwendung einer einheitlicher Notation. Anhand von zahlreichen Beispielen werden die verschiedenen Eigenschaften und Fakten illustriert und diskutiert.<br />

Abstract argumentation is an attempt to formalise the process of human argumentation, which is commonly used in everyday life for reasoning about knowledge and beliefs as well as for exchanging the information. This technique can be then used for solving many problems in the area of artificial intelligence, but also in the theory of dialogue game or as a tool for comparing different non-monotonic logics.<br />The theory of argumentation tries to answer questions of acceptability of a single argument with respect to the rest of its framework, to identify collections of collectively acceptable arguments and discover relations and connections between properties of such collections together with describing the complexity of such tasks. With most of the relevant problems being intractable, the restrictions and extensions of argumentation framework became part of the argumentation as well.<br />This work presents the summary of achieved results using unified notation and it also provides examples to demonstrate properties and facts that are being discussed.