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 propose in the paper a new solution to the so-called Logical Omniscience Problem of epistemic logic. Almost all attempts in the literature to solve this problem consist in weakening the standard epistemic systems: weaker systems are considered where the agents do not possess the full reasoning capacities of ideal reasoners. We shall argue that this solution is not satisfactory: in this way omniscience can be avoided, but many intuitions about the concepts of knowledge and belief get lost. We shall show that axioms for epistemic logics must have the following form: if the agent knows all premises of a valid inference rule, and if she thinks hard enough, then she will know the conclusion. To formalize such an idea, we propose to \dynamize' epistemic logic, that is, to introduce a dynamic component into the language. We develop a logic based on this idea and show that it is suitable for formalizing the notion of actual, or explicit knowledge.

Der Begriff ``Agent'' hat sich als eine sehr nützliche Abstraktion erwiesen, um verschiedene Problembereiche auf eine intuitive und natürliche Art und Weise zu konzeptualisieren. Intelligente Agenten haben daher Anwendung gefunden in verschiedenen Teilbereichen der Informatik. Zur Modellierung werden intelligente Agenten meist als intentionale Systeme aufgefaßt und mit Hilfe von mentalistischen Begriffen wie Wissen, Glauben (oder Überzeugung), Wunsch, Pflicht, Intention usw. beschrieben. Unter diesen mentalen Begriffen gehören die epistemischen Begriffe (d.h., Wissen und Glauben) zu den wichtigsten und wurden auch am intensivsten untersucht. Zur Modellierung von Wissen und Glauben werden in der Regel modale epistemische Logiken verwendet. Solche Systeme sind aber nicht geeignet, um ressourcenbeschränkte Agenten zu beschreiben, weil sie zu starke Annahmen bezüglich der Rationalität von Agenten machen. Zum Beispiel wird angenommen, daß Agenten alle logischen Wahrheiten sowie alle Konsequenzen seines Wissens kennen. Dieses Problem ist bekannt als das Problem der logischen Allwissenheit (``logical omniscience problem''). Da alle Agenten grundsätzlich nur über begrenzte Ressourcen (wie z.B. Zeit, Information, Speicherplatz) verfügen, können sie nur eine begrenzte Menge von Informationen verarbeiten. Daher müssen alternative Modelle entwickelt werden, um Agenten realistisch modellieren zu können (siehe Kapitel 2). Daß modale epistemische Logik für die Formalisierung des ressourcenbeschränkten Schließens (``resource-bounded reasoning'') nicht geeignet ist, wird als ein offenes Problem der Agententheorien anerkannt. Es gibt bisher aber keine brauchbaren Alternativen zur Modallogik. Die meisten Ansätze zur Lösung des logischen Allwissenheitsproblems versuchen, Wissen und Glauben mit Hilfe schwacher Modallogiken zu beschreiben. Solche Versuche sind nicht befriedigend, da sie eine willkürliche Einschränkung der Rationalität der Agenten zur Folge haben (siehe Kapitel 3). Mein Ziel ist es, einen Rahmen für das ressourcenbeschränktes Schließen über Wissen und Glauben zu entwickeln. Damit soll eine solide Grundlage für Theorien intelligenter Agenten geschaffen werden. Als Nebenergebnis wird das logische Allwissenheitsproblem auf eine sehr intuitive Art und Weise gelöst: obwohl Agenten rational sind und alle logischen Schlußregeln anwenden können, sind sie nicht logisch allwissend, weil ihnen nicht genügend Ressourcen zu Verfügung stehen, um alle logischen Konsequenzen ihres Wissens zu ziehen. Im Kapitel 4 wird eine Reihe von Logiken vorgestellt, die den Begriff des expliziten Wissens formalisieren. Es wird eine Lösung des Problems der logischen Allwissenheit der epistemischen Logik vorgeschlagen, die die Rationalität der Agenten nicht willkürlich einschränkt. Der Grundgedanke dabei ist der folgende. Ein Agent kennt die logischen Konsequenzen seines Wissens nur dann, wenn er sie tatsächlich hergeleitet hat. Wenn ein Agent alle Prämissen einer gültigen Schlußregel kennt, kennt er nicht notwendigerweise die Konklusion: er kennt sie nur nach der Anwendung der Regel. Wenn er den Schluß nicht ziehen kann, z.B. weil er nicht die notwendigen Ressourcen dazu hat, wird sein Wissen nicht um diese herleitbare Information erweitert. Die Herleitung neuer Informationen wird als die Ausführung mentaler Handlungen aufgefaßt. Mit Hilfe einer Variante der dynamischen Logik können diese Handlungen beschrieben werden. Im Kapitel 5 werden Systeme für das ressourcenbeschränkte Schließen über Wissen und Glauben entwickelt, die auch quantitative Bedingungen über die Verfügbarkeit von Ressourcen modellieren können. Mit Hilfe dieser Logiken können Situationen beschrieben werden, wo Agenten innerhalb einer bestimmten Zeitspanne entscheiden müssen, welche Handlungen sie ausführen sollen. Der Ansatz besteht darin, epistemische Logik mit Komplexitätstheorie zu verbinden. Mit Hilfe einer Komplexitätsanalyse kann ein Agent feststellen, ob ein bestimmtes Problem innerhalb vorgegebener Zeit lösbar ist. Auf der Grundlage dieses Wissens kann er dann die für die Situation geeignete Entscheidung treffen. Damit ist es gelungen, eine direkte Verbindung zwischen dem Wissen eines Agenten und der Verfügbarkeit seiner Ressourcen herzustellen. / One of the principal goals of agent theories is to describe realistic, implementable agents, that is, those which have actually been constructed or are at least in principle implementable. That goal cannot be reached if the inherent resource-boundedness of agents is not treated correctly. Since the modal approach to epistemic logic is not suited to formalize resource-bounded reasoning, the issue of resource-boundedness remains one of the main foundational problems of any agent theory that is developed on the basis of modal epistemic logic. My work is an attempt to provide theories of agency with a more adequate epistemic foundation. It aims at developing theories of mental concepts that make much more realistic assumptions about agents than other theories. The guiding principle of my theory is that the capacities attributed to agents must be empirically verifiable, that is, it must be possible to construct artificial agents which satisfy the specifications determined by the theory. As a consequence, the unrealistic assumption that agents have unlimited reasoning capacities must be rejected. To achieve the goal of describing resource-bounded agents accurately, the cost of reasoning must be taken seriously. In the thesis I have developed a framework for modeling the relationship between knowledge, reasoning, and the availability of resources. I have argued that the correct form of an axiom for epistemic logic should be: if an agent knows all premises of a valid inference rule and if he performs the right reasoning, then he will know the conclusion as well. Because reasoning requires resources, it cannot be safely assumed that the agent can compute his knowledge if he does not have enough resources to perform the required reasoning. I have demonstrated that on the basis of that idea, the problems of traditional approaches can be avoided and rich epistemic logics can be developed which can account adequately for our intuitions about knowledge.

An understanding of cryptographic protocols requires that we examine the knowledge of protocol participants and adversaries: When a participant receives a message, does she know who sent it? Does she know that the message is fresh, and not merely a replay of some old message? Does a network spy know who is talking to whom? This thesis studies logics of knowledge and cryptography. Specifically, the thesis addresses the problem of how to make the concept of knowledge reflect feasible computability within a Kripke-style semantics. The main contributions are as follows. 1. A generalized Kripke semantics for first-order epistemic logic and cryptography, where the later is modeled using private constants and arbitrary cryptographic operations, as in the Applied Pi-calculus. 2. An axiomatization of first-order epistemic logic which is sound and complete relative to an underlying theory of cryptographic terms, and to an omega-rule for quantifiers. Besides standard axioms and rules from first-order epistemic logic, the axiomatization includes some novel axioms for the interaction between knowledge and cryptography. 3. Epistemic characterizations of static equivalence and Dolev-Yao message deduction. 4. A generalization of Kripke semantics for propositional epistemic logic and symmetric cryptography. 5. Decidability, soundness and completeness for propositional BAN-like logics with respect to message passing systems. Completeness and decidability are generalised to logics induced from an arbitrary base of protocol specific assumptions. 6. An epistemic definition of message deduction. The definition lies between weaker and stronger versions of Dolev-Yao deduction, and coincides with weaker Dolev-Yao regarding all atomic messages. For composite messages, the definition withstands a well-known counterexample to Dolev-Yao deduction. 7. Protocol examples using mixes, a Crowds style protocol, and electronic payments. / QC 20100524

Der Begriff ``Agent'''' hat sich als eine sehr nützliche Abstraktion erwiesen, um verschiedene Problembereiche auf eine intuitive und natürliche Art und Weise zu konzeptualisieren. Intelligente Agenten haben daher Anwendung gefunden in verschiedenen Teilbereichen der Informatik. Zur Modellierung werden intelligente Agenten meist als intentionale Systeme aufgefaßt und mit Hilfe von mentalistischen Begriffen wie Wissen, Glauben (oder Überzeugung), Wunsch, Pflicht, Intention usw. beschrieben. Unter diesen mentalen Begriffen gehören die epistemischen Begriffe (d.h., Wissen und Glauben) zu den wichtigsten und wurden auch am intensivsten untersucht. Zur Modellierung von Wissen und Glauben werden in der Regel modale epistemische Logiken verwendet. Solche Systeme sind aber nicht geeignet, um ressourcenbeschränkte Agenten zu beschreiben, weil sie zu starke Annahmen bezüglich der Rationalität von Agenten machen. Zum Beispiel wird angenommen, daß Agenten alle logischen Wahrheiten sowie alle Konsequenzen seines Wissens kennen. Dieses Problem ist bekannt als das Problem der logischen Allwissenheit (``logical omniscience problem''''). Da alle Agenten grundsätzlich nur über begrenzte Ressourcen (wie z.B. Zeit, Information, Speicherplatz) verfügen, können sie nur eine begrenzte Menge von Informationen verarbeiten. Daher müssen alternative Modelle entwickelt werden, um Agenten realistisch modellieren zu können (siehe Kapitel 2). Daß modale epistemische Logik für die Formalisierung des ressourcenbeschränkten Schließens (``resource-bounded reasoning'''') nicht geeignet ist, wird als ein offenes Problem der Agententheorien anerkannt. Es gibt bisher aber keine brauchbaren Alternativen zur Modallogik. Die meisten Ansätze zur Lösung des logischen Allwissenheitsproblems versuchen, Wissen und Glauben mit Hilfe schwacher Modallogiken zu beschreiben. Solche Versuche sind nicht befriedigend, da sie eine willkürliche Einschränkung der Rationalität der Agenten zur Folge haben (siehe Kapitel 3). Mein Ziel ist es, einen Rahmen für das ressourcenbeschränktes Schließen über Wissen und Glauben zu entwickeln. Damit soll eine solide Grundlage für Theorien intelligenter Agenten geschaffen werden. Als Nebenergebnis wird das logische Allwissenheitsproblem auf eine sehr intuitive Art und Weise gelöst: obwohl Agenten rational sind und alle logischen Schlußregeln anwenden können, sind sie nicht logisch allwissend, weil ihnen nicht genügend Ressourcen zu Verfügung stehen, um alle logischen Konsequenzen ihres Wissens zu ziehen. Im Kapitel 4 wird eine Reihe von Logiken vorgestellt, die den Begriff des expliziten Wissens formalisieren. Es wird eine Lösung des Problems der logischen Allwissenheit der epistemischen Logik vorgeschlagen, die die Rationalität der Agenten nicht willkürlich einschränkt. Der Grundgedanke dabei ist der folgende. Ein Agent kennt die logischen Konsequenzen seines Wissens nur dann, wenn er sie tatsächlich hergeleitet hat. Wenn ein Agent alle Prämissen einer gültigen Schlußregel kennt, kennt er nicht notwendigerweise die Konklusion: er kennt sie nur nach der Anwendung der Regel. Wenn er den Schluß nicht ziehen kann, z.B. weil er nicht die notwendigen Ressourcen dazu hat, wird sein Wissen nicht um diese herleitbare Information erweitert. Die Herleitung neuer Informationen wird als die Ausführung mentaler Handlungen aufgefaßt. Mit Hilfe einer Variante der dynamischen Logik können diese Handlungen beschrieben werden. Im Kapitel 5 werden Systeme für das ressourcenbeschränkte Schließen über Wissen und Glauben entwickelt, die auch quantitative Bedingungen über die Verfügbarkeit von Ressourcen modellieren können. Mit Hilfe dieser Logiken können Situationen beschrieben werden, wo Agenten innerhalb einer bestimmten Zeitspanne entscheiden müssen, welche Handlungen sie ausführen sollen. Der Ansatz besteht darin, epistemische Logik mit Komplexitätstheorie zu verbinden. Mit Hilfe einer Komplexitätsanalyse kann ein Agent feststellen, ob ein bestimmtes Problem innerhalb vorgegebener Zeit lösbar ist. Auf der Grundlage dieses Wissens kann er dann die für die Situation geeignete Entscheidung treffen. Damit ist es gelungen, eine direkte Verbindung zwischen dem Wissen eines Agenten und der Verfügbarkeit seiner Ressourcen herzustellen. / One of the principal goals of agent theories is to describe realistic, implementable agents, that is, those which have actually been constructed or are at least in principle implementable. That goal cannot be reached if the inherent resource-boundedness of agents is not treated correctly. Since the modal approach to epistemic logic is not suited to formalize resource-bounded reasoning, the issue of resource-boundedness remains one of the main foundational problems of any agent theory that is developed on the basis of modal epistemic logic. My work is an attempt to provide theories of agency with a more adequate epistemic foundation. It aims at developing theories of mental concepts that make much more realistic assumptions about agents than other theories. The guiding principle of my theory is that the capacities attributed to agents must be empirically verifiable, that is, it must be possible to construct artificial agents which satisfy the specifications determined by the theory. As a consequence, the unrealistic assumption that agents have unlimited reasoning capacities must be rejected. To achieve the goal of describing resource-bounded agents accurately, the cost of reasoning must be taken seriously. In the thesis I have developed a framework for modeling the relationship between knowledge, reasoning, and the availability of resources. I have argued that the correct form of an axiom for epistemic logic should be: if an agent knows all premises of a valid inference rule and if he performs the right reasoning, then he will know the conclusion as well. Because reasoning requires resources, it cannot be safely assumed that the agent can compute his knowledge if he does not have enough resources to perform the required reasoning. I have demonstrated that on the basis of that idea, the problems of traditional approaches can be avoided and rich epistemic logics can be developed which can account adequately for our intuitions about knowledge.