Dans cette thèse, nous proposons des modèles logiques pour la représentation des croyances et leur changement dans un cadre multi-agent, en insistant sur l'importance de se fixer un point de vue particulier pour la modélisation. A cet égard, nous distinguons deux approches différentes: l'approche externe, où le modélisateur est quelqu'un d'externe à la situation; l'approche interne, où le modélisateur est l'un des agents. Nous proposons une version interne de la logique épistémique dynamique (avec des modèles d'événements), ce qui nous permet de généraliser facilement la théorie de la révision des croyances d'AGM au cas multi-agent. Ensuite, nous mod´elisons les dynamismes logiques complexes qui soustendent notre interprétation des événements en introduisant des probabilités et des infinitésimaux. Finalement, nous proposons un formalisme alternatif qui n'utilise pas de modèle d'événement mais qui introduit à la place un opérateur d'événement inverse.

A área de revisão de crenças estuda a forma como agentes racionais operam sobre seus conhecimentos, permitindo que estes evoluam à vista de novas informações. Muitas das formas de manipulação do conhecimento hoje utilizadas foram desenvolvidas tendo como base o paradigma estabelecido por Alchourrón, Gärdenfors e Makinson em 1985, que evoluiu nas últimas décadas sob influência de diversas correntes de pensamento, dando origem a múltiplas abordagens para a estruturação de operadores sobre crenças. Esta dissertação limita-se à análise das duas principais construções de operadores sobre bases de crenças, bem como suas propriedades e relações. A partir desta análise, foi construído um framework computacional que permitiu a análise empírica do comportamento destas construções em diversos casos gerados, de modo a averiguar a eficiência real dos algoritmos envolvidos. Também são expostos detalhes do framework, construído de forma flexível para permitir sua reutilização em trabalhos futuros. / Belief revision studies the ways rational agents change their beliefs, allowing them to evolve when exposed to new information. Many of the belief change forms currently used were developed based on the paradigm established by Alchourrón, Gärdenfors and Makinson in 1985, which evolved over the last decades under the influence of several distinct fields, originating multiple approaches to implement operators on beliefs. This dissertation is limited to the analysis of the two main constructions of operators on belief bases, including their properties and relations. Based on this analysis, a computational framework was created to allow the empirical analysis of the behavior of these constructions on generated scenarios, in order to measure the real eficiency of the algorithms concerned. It also describes the framework, built aiming for exibility in order to allow it\'s usage in future works.

Orientador: Marcelo Esteban Coniglio / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas / Made available in DSpace on 2018-08-25T18:45:14Z (GMT). No. of bitstreams: 1 Testa_RafaelRodrigues_D.pdf: 1707390 bytes, checksum: 77a5315394cfd4052cf1fe8733d0559c (MD5) Previous issue date: 2014 / Resumo: A Revisão de Crenças estuda como agentes racionais mudam suas crenças ao receberem novas informações. O sistema AGM, trabalho mais influente desta área apresentado por Alchourrón, Gärdenfos e Makinson, postula critérios de racionalidade para os diferentes tipos de mudança de crenças e oferece construções explícitas para tais - a equivalência entre os postulados e operações é chamado de teroema da representação. Trabalhos recentes mostram como o paradigma AGM pode ser compatível com diferentes lógicas não-clássicas, o que é chamado de AGM-compatibilidade - este é o caso da família de lógicas paraconsistentes que analisamos, as Lógicas da Inconsistência Formal (LFIs, da sigla em inglês). A despeito da AGM-compatibilidade, ao se partir de uma nova lógica sua racionalidade subjacente deve ser entendida e sua linguagem deve ser efetivamente usada. Propomos assim novas construções que de fato capturam a intuição presente na LFIs - é o que chamamos de sistema AGMo. Com isso, possibilitamos a estas lógicas uma nova interpretação, na esteira da epistemologia formal. Em uma abordagem alternativa, ao se partir da AGM-compatibilidade os resultados AGM podem ser diretamente aplicados às LFIs - o que chamamos de sistema AGMp. Em ambas abordagens, provamos os respectivos teoremas da representação sempre que necessário / Abstract: Belief Revision studies how rational agents change their beliefs when they receive new information. The AGM system, most influential work in this area of study investigated by Alchourrón, Gärdenfos and Makinson, postulates rationality criteria for different types of belief change and provides explicit constructions for them - the equivalence between the postulates and operations is called representation theorem. Recent studies show how the AGM paradigm can be compliant with different non-classical logics, which is called the AGM-compliance - this is the case of the paraconsistent logics family we analyze in this thesis, the Logics of Formal Inconsistency (LFIs). Despite the AGM-compliance, when a new logic is taken into account its underlying rationality must be understood and its language should be used. In that way new constructions are proposed, which actually captures the intuition of LFIs - what we call the AGMo system. Thus, we provide a new interpretation for these logics, more in line with formal epistemology. In an alternative approach, by considering the AGM-compliance, we show how the AGM results can be directly applied to LFIs -- resulting the AGMp system. In both approaches, we prove the corresponding representation theorems where needed / Doutorado / Filosofia / Doutor em Filosofia

A área de revisão de crenças estuda a forma como agentes racionais operam sobre seus conhecimentos, permitindo que estes evoluam à vista de novas informações. Muitas das formas de manipulação do conhecimento hoje utilizadas foram desenvolvidas tendo como base o paradigma estabelecido por Alchourrón, Gärdenfors e Makinson em 1985, que evoluiu nas últimas décadas sob influência de diversas correntes de pensamento, dando origem a múltiplas abordagens para a estruturação de operadores sobre crenças. Esta dissertação limita-se à análise das duas principais construções de operadores sobre bases de crenças, bem como suas propriedades e relações. A partir desta análise, foi construído um framework computacional que permitiu a análise empírica do comportamento destas construções em diversos casos gerados, de modo a averiguar a eficiência real dos algoritmos envolvidos. Também são expostos detalhes do framework, construído de forma flexível para permitir sua reutilização em trabalhos futuros. / Belief revision studies the ways rational agents change their beliefs, allowing them to evolve when exposed to new information. Many of the belief change forms currently used were developed based on the paradigm established by Alchourrón, Gärdenfors and Makinson in 1985, which evolved over the last decades under the influence of several distinct fields, originating multiple approaches to implement operators on beliefs. This dissertation is limited to the analysis of the two main constructions of operators on belief bases, including their properties and relations. Based on this analysis, a computational framework was created to allow the empirical analysis of the behavior of these constructions on generated scenarios, in order to measure the real eficiency of the algorithms concerned. It also describes the framework, built aiming for exibility in order to allow it\'s usage in future works.

This paper investigates the relationship between the theory of belief revision and Lindenbaum-Tarski algebras for propositional logic. The intent is to represent the revision function described by the AGM-postulates algebraically. The AGM theory is based on deductively closed sets, which are characterizable as generated filters in the algebra as well as depictable in the corresponding Hasse diagram. This fact is shown by proving that a partial order is definable for the algebra, that this order is the consequence relation of propositional calculus and that the generated filters are deductively closed. Furthermore, an alternative, but equivalent approach to the AGM theory is introduced, the revision proposed by Katsuno and Mendelzon, which characterizes the deductively closed sets as propositional formulae. This correspondence follows naturally from the behaviour of filters and can be applied without problems to define the functions of the AGM framework in the Lindenbaum-Tarski algebra. The visualization of partially ordered sets as a Hasse diiagram is used to depict an example of a belief revision. Lastly, some combinatorical calculations are introduced to determine the number of possible solution candidates for a belief revision.

We live in an era of data and information, where an immeasurable amount of discoveries, findings, events, news, and transactions are generated every second. Governments, companies, or individuals have to employ and process all that data for knowledge-based decision-making (i.e. a decision-making process that uses predetermined criteria to measure and ensure the optimal outcome for a specific topic), which then prompt them to view the knowledge as valuable resource. In this knowledge-based view, the capability to create and utilize knowledge is the key source of an organization or individual’s competitive advantage. This dynamic nature of knowledge leads us to the study of belief revision (or belief change), an area which emerged from work in philosophy and then impacted further developments in computer science and artificial intelligence. In belief revision area, the AGM postulates by Alchourrón, Gärdenfors, and Makinson continue to represent a cornerstone in research related to belief change. Katsuno and Mendelzon (K&M) adopted the AGM postulates for changing belief bases and characterized AGM belief base revision in propositional logic over finite signatures. In this thesis, two research directions are considered. In the first, by considering the semantic point of view, we generalize K&M’s approach to the setting of (multiple) base revision in arbitrary Tarskian logics, covering all logics with a classical model-theoretic semantics and hence a wide variety of logics used in knowledge representation and beyond. Our generic formulation applies to various notions of “base”, such as belief sets, arbitrary or finite sets of sentences, or single sentences. The core result is a representation theorem showing a two-way correspondence between AGM base revision operators and certain “assignments”: functions mapping belief bases to total — yet not transitive — “preference” relations between interpretations. Alongside, we present a companion result for the case when the AGM postulate of syntax-independence is abandoned. We also provide a characterization of all logics for which our result can be strengthened to assignments producing transitive preference relations (as in K&M’s original work), giving rise to two more representation theorems for such logics, according to syntax dependence vs. independence. The second research direction in this thesis explores two approaches for revising description logic knowledge bases under fixed-domain semantics, namely model-based approach and individual-based approach. In this logical setting, models of the knowledge bases can be enumerated and can be computed to produce the revision result, semantically. We show a characterization of the AGM revision operator for this logic and present a concrete model-based revision approach via distance between interpretations. In addition, by weakening the KB based on certain domain elements, a novel individual-based revision operator is provided as an alternative approach.

As Lógicas de Descrição são usadas como base para a linguagem OWL, padrão para representação de ontologias na web. No entanto, conhecimento não é estático e, com tal dinamismo, o estudo de revisão de crenças e sua correta e adequada aplicação tornam-se muito importantes. Neste trabalho, pretendemos desenvolver uma ferramenta para revisão de ontologias como um plug-in para o Protégé, o editor de ontologias mais utilizado atualmente. / Description Logics are the basis for OWL language, which is the standard to represent ontologies on the web. However, knowledge is usually not satic and its dynamics brings the importance of belief revision and its correct and proper application. In this work, we intend to develop a tool for revising ontologies as a plug-in for Protégé, the most used ontology editor nowadays.

A area de revisão de crenças estuda como agentes racionais mudam suas crencas ao receberem novas informações. O marco da area de revisão de crenças foi a publicacão do trabalho de Alchourron, Gardenfors e Makinson. Nesse trabalho conhecido como paradigma AGM foram denidos criterios de racionalidade para tipos de mudanca de crencas. Desde então, a área de revisão de crenças foi influenciada por diversas disciplinas como filosoa, computacão e direito. Paralelamente ao desenvolvimento da area de revisão de crenças, os últimos 20 anos foram marcados por um grande avanço no estudo das logicas de descrição. Tal avanço, impulsionado pelo desenvolvimento da web-semântica, levou a adoção de linguagens inspiradas em logicas de descrição (OWL) como padrão para se representar ontologias na web. Nessa tese tratamos do problema de aplicar a teoria da revisão de crenças a lógicas não clássicas e especialmente a logicas de descric~ao. Trabalhos recentes mostraram que o paradigma AGM e incompatvel com diversas logicas de descricão. Estendemos esses resultados mostrando outras lógicas que não são compatíveis com o paradigma AGM. Propomos formas de aplicar a teoria de revisão tanto em bases quanto em conjuntos de crencas a essas logicas. Alem disso, usamos algoritmos conhecidos da área de depuração de ontologias para implementar operações em bases de crenças. / Belief revision theory studies how rational agents change their beliefs after receiving new information. The most in uential work in this area is the paper of Alchourron, Gardenfors and Makinson. In this work, known as AGM paradigm rationality criteria for belief change were dened. Since then, the eld has been in uenced by many areas like philosophy, computer science and law. Parallel to the development of belief revision eld, in the past 20 years there was a huge grow in the study of description logics. The climax of this development was the adoption of OWL (a language based on description logics) as the standard language to represent ontologies on the web. In this work we deal with the problem of applying belief revision in to non-classical logics, specially description logics. Recent works showed that the AGM paradigm is not compliant with several description logics. We have extended this work by showing that other logics are not compliant with AGM paradigm. Furthermore, we propose alternative ways to apply belief revision techniques to these logics. Finally, we show that well known algorithms from the area of ontology debugging eld can be used to implement the proposed constructions.

As Lógicas de Descrição são usadas como base para a linguagem OWL, padrão para representação de ontologias na web. No entanto, conhecimento não é estático e, com tal dinamismo, o estudo de revisão de crenças e sua correta e adequada aplicação tornam-se muito importantes. Neste trabalho, pretendemos desenvolver uma ferramenta para revisão de ontologias como um plug-in para o Protégé, o editor de ontologias mais utilizado atualmente. / Description Logics are the basis for OWL language, which is the standard to represent ontologies on the web. However, knowledge is usually not satic and its dynamics brings the importance of belief revision and its correct and proper application. In this work, we intend to develop a tool for revising ontologies as a plug-in for Protégé, the most used ontology editor nowadays.

Η Αλλαγή Πεποιθήσεων είναι το πεδίο που ασχολείται, μελετά και τυποποιεί ένα πλήθος διαδικασιών της συλλογιστικής σκέψης. Οι θεμελιώδεις αρχές της βρίσκονται σε διάφορα φιλοσοφικά συστήματα της περιόδου της αρχαιότητας. Ωστόσο, η σύγχρονη προβληματική που αναπτύσσεται γύρω από το πεδίο αυτό και που καλείται να αντιμετωπίσει εντάσσεται στην ευρύτερη περιοχή της Αναπαράστασης της Γνώσης. Στα μέσα της δεκαετίας του 80 και ύστερα από την προσπάθεια μετάβασης σε πιο συστηματικές και μαθηματικές προσεγγίσεις, η Αλλαγή Πεποιθήσεων αποκτά την τελική της μορφή. Ο όρος Αλλαγή διαιρείται σε τρεις ευρείες υπό-ενότητες: την πρόσθεση, την αφαίρεση και την αναθεώρηση. Η πρόσθεση αναφέρεται στη συλλογή νέων πληροφοριών (επέκταση πεποιθήσεων), η αφαίρεση την απώλεια πληροφορίας, ενώ η αναθεώρηση ερμηνεύει τη μερική ή ολική αλλαγή στο σύνολο των πεποιθήσεών μας, εξαιτίας της εμφάνισης μίας νέας πεποίθησης. Κάθε διαδικασία Αλλαγής συνοδεύεται από ένα σύνολο ορθολογικών αξιωμάτων. Τα αξιώματα διατυπώθηκαν με κύριο σκοπό την ομαδοποίηση, ταξινόμηση και περιορισμό των συλλογιστικών μας ενεργειών. Εκτός από τους τύπους αλλαγών και τα σύνολα των αξιωμάτων που αναφέρθηκαν στο χώρο της Αλλαγής Πεποιθήσεων υπάρχουν και άλλες σημαντικές - συμπληρωματικές διαδικασίες. Μία από τις πιο γνωστές και επωφελείς είναι αυτή της Επαναλαμβανόμενης Αναθεώρησης. Ενώ η απλή αναθεώρηση ερμηνεύει καταστάσεις που προξενούνται από την εμφάνιση μίας και μόνο πληροφορίας, η επαναλαμβανόμενη αναθεώρηση διασαφηνίζει περιπτώσεις μάθησης μέσα από το φάσμα των διαδοχικών πεποιθήσεων. Η παρούσα διατριβή θα μπορούσε να διαιρεθεί σε τρεις μεγάλες κατηγορίες. Η πρώτη εξετάζει συστηματικά τις διάφορες μεθόδους και τεχνικές που αναφέρονται στη διεθνή βιβλιογραφία. Η δεύτερη περιλαμβάνει την κυριότερη ερευνητική μας συνεισφορά καθώς και οι προτάσεις μας πάνω σε ανοικτά προβλήματα της Αλλαγής των Πεποιθήσεων. Πιο συγκεκριμένα, στο αρχικό στάδιο της έρευνάς μας αποτυπώνεται η προσπάθεια σύνδεσης της αναθεώρησης με την επαναλαμβανόμενη αναθεώρηση πεποιθήσεων. Η σύνδεση αυτή επιτυγχάνεται με την εισαγωγή ενός νέου αξιώματος που ονομάζουμε αξίωμα επαναλαμβανόμενης ανάκτησης. Αποδεικνύεται ότι το αξίωμα της επαναλαμβανόμενης ανάκτησης μπορεί να χρησιμοποιηθεί σε πολλές περιπτώσεις κατά τις οποίες το δεύτερο αξίωμα (DP2) των Darwiche και Pearl χαρακτηρίζεται αρκετά ισχυρό. Αποδεικνύουμε επίσης την ορθότητα και πληρότητα του παραπάνω αξιώματος μέσα από το σύστημα σφαιρών του Adam Grove. Στη συνέχεια η έρευνά μας στρέφεται στην προσπάθεια σύνδεσης δύο πολύ σημαντικών περιοχών στην αλλαγή πεποιθήσεων: την Επαναλαμβανόμενη και τη Relevance-Sensitive αναθεώρηση πεποιθήσεων. Τα αποτελέσματα της απόδειξης αφενός αποκαλύπτουν την ύπαρξη μη-συνέπειας μεταξύ τους αξιώματος (P) για τη Relevanse-Sensitive αναθεώρηση πεποιθήσεων με κάθε ένα από τα (DP) αξιώματα της επαναλαμβανόμενης αναθεώρησης πεποιθήσεων, αφετέρου αξιώνουν μία αναγκαία και γενικότερη αποκατάσταση στα τυπικά μοντέλα της αλλαγής πεποιθήσεων. Ακόμη μπορεί να αποδοθεί στη δική μας έρευνα και κάτι διαφορετικό, σε σχέση με τις άλλες: ότι η διαδικασία της αφαίρεσης πεποιθήσεων βασίζεται σε Horn Clauses. Ωστόσο, η αμιγής ερευνητική μας προσπάθεια αναφέρεται την παροχή σημασιολογίας βασιζόμενη σε διατάξεις πιθανών κόσμων για τη διαδικασία του e-contraction που εισήγαγε ο James Delgrande. Η Τρίτη κατηγορία, τέλος, αποβλέπει στην παρουσίαση της κλασσικής θεωρίας της Αναθεώρησης Πεποιθήσεων μέσα από την εφαρμογή της στην επιστήμη των υπολογιστών και πιο συγκεκριμένα, μέσω του Σημασιολογικού Ιστού. / Belief Change is an area that studies and standardizes several reasoning processes. However, the problems it has to confront rest in the wider area of Knowledge Representation. In the mid-1980s and after a transition effort to more systematic and mathematical Approaches, the Belief Change gets into its final form. The term “change” splits in three wide subgroups: expansion, contraction and revision. The expansion regards the collection of new information (belief expansion), while contraction concerns the loss of information. Finally, the revision explains the partial or total change in our beliefs, deriving from the appearance of new information. Every Change process is coupled with several rational postulates. Those were mainly formulated to group, classify and constrain our reasoning. Apart from the change formulas and the postulates mentioned above, in the field of Belief Change there are other important – additional processes. One of the most known and useful is the Iterated Revision. While the simple Revision explains conditions that are induced from the emergence of one and only information, the Iterated Revision clarifies cases of learning through the spectrum of successive beliefs. The present dissertation is classified in three major categories. The first one concerns the systematic study of several methods and techniques found in the international bibliography. The second incorporates our main contribution in research and our propositions with regard in open problems of the Belief Change. More specifically, the initial stage of our research is an effort to connect the revision with the iterated belief revision. This connection is achieved with the introduction of a new postulate called “iterated recovery postulate”. It is also established that the iterated recovery postulate (IR) can be used in many cases where the second postulate DP2, by Darwiche and Pearl, is qualified as rather strong. Moreover, we prove hereby that the postulate is sound and complete through the Adam Grove’s System of Spheres. Our research continues to connect two very important areas in the Belief Change: the Iterated and the Relevance-Sensitive belief revision. The conclusions of this proof reveal the inconsistency between the (P) postulate, regarding the Relevance-Sensitive belief revision, with “each and every one” of the DP postulates of the iterated belief revision. Likewise, they urge for a broad and imperative recovery of the “belief change” typical models. Unlike others, our contribution in research has to do with the belief contraction process, based on Horn Clauses. Our pure research regards the provision of semantics based on possible worlds orderings for the process of e-contraction, introduced by James Delgrande. Finally, the third category tries to present the classical theory of Belief Revision through its application in the computer science and specifically through the Semantic Web.