There is a recent trend of extending epistemic logic (EL) with dynamic operators that allow to express the evolution of knowledge and belief induced by knowledge-changing actions. The most basic such extension is public announcement logic (PAL), which is obtained from EL by adding an operator for truthful publix announcements. In this paper, we consider the computational complexity of PAL and show that it coincides with that of EL. This holds in the single- and multi-agent case, and also in the presence of common knowledge operators. We also prove that there are properties that can be expressed exponentially more succint in PAL than in EL. This shows that, despite the known fact that PAL and EL have the same expressive power, ther eis a benefit in adding the public announcement operator to EL: it exponentially increases the succinctness of formulas without having negative effects on computational complexity.

Le projet de cette thèse émane du constat d'une scission entre épistémologie d'une part et logique épistémique d'autre part. Si des tentatives de conciliation se sont avérées fructueuses, nous explorons ici la possibilité d'une réconciliation entre épistémologie et logique épistémique à travers l'argumentation.Étudier la logique épistémique au sein d'une pratique argumentative, c'est-À-Dire au sein de dialogues, nous permet de bénéficier d'un cadre d'étude dynamique pour explorer le dynamisme et la signification du langage de la logique épistémique. Nous montrons que cette conciliation de l'épistémologie et de la logique épistémique dans une pratique argumentative est pertinente dans le domaine juridique car elle offre une approche originale de la notion de condition dans le droit. / The project of this thesis stems from the observation of a split between epistemology and epistemic logic.If some attempts at conciliation have been successful, here we explore the possibility of reconciliation between epistemology and epistemic logic through argumentation.Studying epistemic logic in argumentative practice, that is to say in dialogues, enables us to benefit from a dynamic framework to explore the dynamics and the meaning of the language of epistemic logic.We show that this reconciliation of epistemology and epistemic logic in an argumentative practice is relevant in the legal field because it offers an original approach to the notion of condition in law.

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

First, we consider different kinds of representation of uncertainty and the meth- ods for updating each of them by conditioning. We focus on the generic frame- work of (conditional) plausibility spaces, since it generalises all the introduced representations. Further, we select three frameworks and list the properties that need to be added to a conditional plausibility space in order to recover each of these frameworks. The main goal of this work, however, is to show how public announcement on single-agent plausibility models, ranking structures, and pos- sibility structures realised by their corresponding update mechanisms, can be embedded into the framework of conditional plausibility spaces. At the very end we briefly illustrate a general update model using plausibility measures. Keywords: belief revision, dynamic logic, epistemic logic, plausibility space, pub- lic announcement, uncertainty, update.

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.

The inadequacy of the usual possible world semantics of modal languages when the meaning of 'belief' is attached to the modal operator is discussed. Three other approaches are then investigated. In the case of Moore's autoepistemic logic it becomes possible to compare an agent's beliefs to 'reality', which cannot be done directly in the possible world semantics. Levesque's semantics makes explicit in the object language the notion of 'this is all the information the agent has', which plays an important role in nonmonotonic reasoning. Both of these approaches deal with ideal reasoners. The third approach, Konolige's deduction model, is based on a semantics capable of describing the beliefs of one or more resourcebounded agents. Finally, the AGM postulates for belief revision are discussed. / Computer Science / M.Sc. (Computer Science)

Cette thèse est structurée autour de deux axes d’études : (1) développer des logiques épistémiques formalisant la prise en compte de nouvelles données en présence d'informations incomplètes ou incohérentes ; (2) caractériser les notions de bisimulation sur les modèles de ces nouvelles logiques. Les logiques modales utilisées pour formaliser des raisonnements dans le cadre d’informations incomplètes et incohérentes, telle que la logique modale de contingence, sont généralement plus faibles que les logiques modales standards. Nos travaux se basent sur des méthodes logiques, algébriques et co-algébriques / In this Ph.D. dissertation we investigate reasoning about information change in the presence of incomplete or inconsistent information, and the characterisation of notions of bisimulation on models encoding such reasoning patterns. Modal logics for incomplete and inconsistent information are typically weaker than the standard modal logics, such as the modal logic of contingency. We use logical, algebraic and co-algebraic methods to achieve our aims. The dissertation consists of two main parts. The first part focusses on reasoning about information change, and the second part focusses on expressivity and bisimulation. In the following, we give an overview of the contents of this dissertation

Le raisonnement epistémique joue un rôle en théorie de la concurrence de plusieurs manières distinctes mais complémentaires; cette thèse en décrit trois. La première, et presque certainement la moins explorée jusqu'à présent, est l'idée d'utiliser les modalités épistémiques comme éléments d'un langage de programmation. La programmation logique émergea sous le slogan <> et dans le paradigme de la programmation concurrente par contraintes, le lien est manifeste de manière très claire. Dans la première partie de cette thèse, nous explorons le rôle des modalités épistémiques, ainsi que celui des modalités spatiales qui leur sont étroitement liées, en tant que partie intégrante du langage de programmation et non simplement en tant que partie du meta-langage du raisonnement à propos des protocoles. La partie suivante explore une variante de la logique épistémique dynamique adaptée aux systèmes de transitions étiquetés. Contrairement à la partie précédente, on serait tenté de croire que tout ce qu'on pouvait dire à ce sujet a déjà été dit. Cependant, le nouvel ingrédient que nous proposons est un lien étroit entre la logique épistémique et la logique de Hennessy-Milner, cette dernière étant \emph{la} logique des systèmes de transitions étiquetés. Plus précisement, nous proposons une axiomatisation et une preuve d'un théorème de complétude faible, ce qui est conforme au principe général qu'on utilise pour des logiques telles que la logique dynamique mais nécessite des adaptations non triviales. La dernière partie de la thèse se concentre sur l'étude d'agents en interaction dans les processus concurents. Nous présentons une sémantique des jeux pour l'interaction d'agents qui rend manifeste le rôle de la connaissance et du flux d'information dans les interactions entre agents, et qui permet de contrôler l'information disponible aux agents en interaction. Nous utilisons les processus comme support de jeu et définissons des stratégies pour les agents de telle sorte que deux agents qui interagissent conformément à leurs stratégies respectives déterminent l'exécution du processus, rempla{\c}cant ainsi l'ordonnanceur traditionnel. Nous démontrons que des restrictions différentes sur les stratégies réprésentent des quantités d'information différentes disponibles à l'ordonnanceur. Ces restrictions sur les stratégies ont un aspect épistémique explicite, et nous présentons une logique modale pour les stratégies et une caractérisation logique de plusieurs restrictions possibles sur les stratégies. Ces trois approches d'analyse et de représentation de l'information épistémique en théorie de la concurrence apportent une nouvelle manière de comprendre la connaissance des agents dans des processus conncurrents, ce qui est vital dans le monde d'aujourd'hui, dans lequel les systèmes distribués composés de multiples agents sont omniprésents.

The inadequacy of the usual possible world semantics of modal languages when the meaning of 'belief' is attached to the modal operator is discussed. Three other approaches are then investigated. In the case of Moore's autoepistemic logic it becomes possible to compare an agent's beliefs to 'reality', which cannot be done directly in the possible world semantics. Levesque's semantics makes explicit in the object language the notion of 'this is all the information the agent has', which plays an important role in nonmonotonic reasoning. Both of these approaches deal with ideal reasoners. The third approach, Konolige's deduction model, is based on a semantics capable of describing the beliefs of one or more resourcebounded agents. Finally, the AGM postulates for belief revision are discussed. / Computer Science / M.Sc. (Computer Science)

Dans les logiques épistémiques, la connaissance est généralement modélisée par un graphe de mondes possibles, qui correspondent aux alternatives à l'état actuel du monde. Ainsi, les arêtes entre les mondes représentent l'indistinguabilité. Connaître une proposition signifie que cette proposition est vraie dans toutes les alternatives possibles. Les informaticiens théoriques ont cependant remarqué que cela a conduit à plusieurs problèmes, à la fois intuitifs et techniques : plus un agent est ignorant, plus elle a d'alternatives à examiner ; les modèles peuvent alors devenir trop grands pour la vérification de système. Ils ont récemment étudié comment la connaissance pourrait être réduite à la notion de visibilité. Intuitivement, l'idée de base est que quand un agent voit quelque chose, alors elle sait sa valeur de vérité. A l'inverse, toute combinaison de valeurs de vérité des variables non observables est possible pour l'agent. Ces informations d'observabilité permettent de reconstituer la sémantique standard de la connaissance : deux mondes sont indistinguables pour un agent si et seulement si chaque variable observée par cet agent a la même valeur dans les deux mondes. Notre objectif est de démontrer que les logiques épistémiques fondées sur la visibilité constituent un outil approprié pour plusieurs applications importantes dans le domaine de l'intelligence artificielle. Dans le cadre actuel de ces logiques de visibilité, chaque agent a un ensemble de variables propositionnelles qu'elle peut observer ; ces visibilités sont constantes à travers le modèle. Cela accompagne une hypothèse forte : les visibilités sont connues de tous, et sont même connaissance commune. De plus, la construction de la connaissance à partir de la visibilité entraîne des validités contre-intuitives, la plus importante étant que l'opérateur de la connaissance distribue sur les disjonctions de littéraux : si un agent sait que p ou q est vrai, alors elle sait que p est vrai ou que q est vrai, parce qu'elle peut les voir. Dans cette thèse, nous proposons des solutions à ces deux problèmes et les illustrons sur diverses applications telles que la planification épistémique ou les jeux booléens épistémiques, et sur des exemples plus spécifiques tels que le problème des enfants sales ou le problème du bavardage. Nous étudions en outre des propriétés formelles des logiques que nous concevons, fournissant axiomatisations et résultats de complexité. / In epistemic logic, knowledge is usually modelled by a graph of possible worlds, representing the alternatives to the current state of the world. So edges between worlds stand for indistinguishability. To know a proposition means that that proposition is true in all possible alternatives. Theoretical computer scientists however noticed that this led to several issues, both intuitively and technically: the more an agent is ignorant, the more alternatives she must consider; models may then become too big for system verification. They recently investigated how knowledge could be reduced to the notion of visibility. Intuitively, the basic idea is that when an agent sees something, then she knows its truth value. The other way round, any combination of truth values of the non-observable variables is possible for the agent. Such observability information allows us to reconstruct the standard semantics of knowledge: two worlds are indistinguishable for an agent if and only if every variable observed by her has the same value in both worlds. We aim to demonstrate that visibility-based epistemic logics provide a suitable tool for several important applications in the field of artificial intelligence. In the current settings of these logics of visibility, every agent has a set of propositional variables that she can observe; these visibilities are constant across the model. This comes with a strong assumption: visibilities are known to everyone, and are even common knowledge. Moreover, constructing knowledge from visibility brings about counter-intuitive validities, the most important being that the knowledge operator distributes over disjunction of literals: if an agent knows that p or q is true, then she knows that p is true or that q is true because she can see them. In this thesis, we propose solutions to these two problems and illustrate them on various applications such as epistemic planning or epistemic boolean games, and on more specific examples such as the muddy children problem or the gossip problem. We moreover study formal properties of the logics we design, providing axiomatizations and complexity results.