A multi-agent system consists of a collection of agents that interact with each other to fulfil their tasks. Individual agents can have different motivations for engaging in interactions. Also, agents can possibly recognise the goals of the other participants in the interaction. To successfully interact, an agent should exhibit the ability to balance reactivity, pro-activeness (autonomy) and sociability. That is, individual agents should deliberate not only on what they themselves know about the working environment and their desires, but also on what they know about the beliefs and desires of the other agents in their group. Multi-agent systems have proven to be a useful tool for modelling and solving problems that exhibit complex and distributed structures. Examples include real-time traffic control and monitoring, work-flow management and information retrieval in computer networks. There are two broad challenges that the agent community is currently investigating. One is the development of the formalisms for representing the knowledge the agents have about their actions, goals, plans for achieving their goals and other agents. The second challenge is the development of the reasoning mechanisms agents use to achieve autonomy during the course of their interactions. Our research interests lie in a model for the interactions among the agents, whereby the behaviour of the individual agents can be specified in a declarative manner and these specifications can be made executable. Therefore, we investigate the methods that effectively represent the agents' knowledge about their working environment (which includes other agents), to derive unrealised information from the agents' knowledge by considering that the agents can obtain only a partial image of their working environment. The research also deals with the logical reasoning about the knowledge of the other agents to achieve a better interaction. Our approach is to apply the notions of modality and non-monotonic reasoning to formalise and to confront the problem of incomplete and conflicting information when modelling multi-agent systems. The approach maintains the richness in the description of the logical method while providing an efficient and easy-to-implement reasoning mechanism. In addition to the theoretical analysis, we investigate n-person argumentation as an application that benefits from the efficiency of our approach.

Title: Reasoning in Description Logics Author: Mgr. Jaromír Malenko Department: Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague Supervisor: Prof. RNDr. Petr Štěpánek, DrSc.; Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague Keywords: Description logic, Reasoner, Cartesian product, Non-monotonic reasoning Abstract: We deal with several aspects of reasoning in Description Logics. First, since description logic (DL) is a subset of First Order Logic (FOL), we use a FOL reasoner to reason in DL. We implemented dl2fol, a DL reasoner that takes an ontology (a DL theory with rules), translates it into a FOL theory, passes this set of formulae to an underling FOL reasoner, and interprets the result in terms of given ontology. This is an effective method for reasoning with newly introduced language constructors. However, we observed longer running times and that satisfiability of some DL concepts wasn't proved due to FOL undecidability. Second, we extend two DLs by introducing new language construct: cartesian product (CP) of concepts and roles. This allows for expressing relationships, that are not expressible by other means in weaker DLs. We...

Abstract dialectical frameworks (ADFs) are a formalism for representing knowledge about abstract arguments and various logical relationships between them. This work studies ADFs in detail. Firstly, we use the framework of approximation fixpoint theory to define various semantics that are known from related knowledge representation formalisms also for ADFs. We then analyse the computational complexity of a variety of reasoning problems related to ADFs. Afterwards, we also analyse the formal expressiveness in terms of realisable sets of interpretations and show how ADFs fare in comparison to other formalisms. Finally, we show how ADFs can be put to use in instantiated argumentation, where researchers try to assign meaning to sets of defeasible and strict rules. The main outcomes of our work show that in particular the sublanguage of bipolar ADFs are a useful knowledge representation formalism with meaningful representational capabilities and acceptable computational properties.

Conflicting information in an agent's knowledge base may lead to a semantical defect, that is, a situation where it is impossible to draw any plausible conclusion. Finding out the reasons for the observed inconsistency and restoring consistency in a certain minimal way are frequently occurring issues in the research area of knowledge representation and reasoning. In a seminal paper Raymond Reiter proves a duality between maximal consistent subsets of a propositional knowledge base and minimal hitting sets of each minimal conflict -- the famous hitting set duality. We extend Reiter's result to arbitrary non-monotonic logics. To this end, we develop a refined notion of inconsistency, called strong inconsistency. We show that minimal strongly inconsistent subsets play a similar role as minimal inconsistent subsets in propositional logic. In particular, the duality between hitting sets of minimal inconsistent subsets and maximal consistent subsets generalizes to arbitrary logics if the stronger notion of inconsistency is used. We cover various notions of repairs and characterize them using analogous hitting set dualities. Our analysis also includes an investigation of structural properties of knowledge bases with respect to our notions. Minimal inconsistent subsets of knowledge bases in monotonic logics play an important role when investigating the reasons for conflicts and trying to handle them, but also for inconsistency measurement. Our notion of strong inconsistency thus allows us to extend existing results to non-monotonic logics. While measuring inconsistency in propositional logic has been investigated for some time now, taking the non-monotony into account poses new challenges. In order to tackle them, we focus on the structure of minimal strongly inconsistent subsets of a knowledge base. We propose measures based on this notion and investigate their behavior in a non-monotonic setting by revisiting existing rationality postulates, and analyzing the compliance of the proposed measures with these postulates. We provide a series of first results in the context of inconsistency in abstract argumentation theory regarding the two most important reasoning modes, namely credulous as well as skeptical acceptance. Our analysis includes the following problems regarding minimal repairs: existence, verification, computation of one and characterization of all solutions. The latter will be tackled with our previously obtained duality results. Finally, we investigate the complexity of various related reasoning problems and compare our results to existing ones for monotonic logics.

El trabajo realizado en esta tesis pertenece al área de argumentación en inteligencia artificial. La representación de conocimiento en un formalismo basado en argumentación se realiza a través de la especificación de argumentos, cada uno en favor de una conclusión a partir de ciertas premisas. Dado que estas conclusiones pueden estar en contradicción, se producen ataques entre los argumentos. Luego, la evaluación de toda la información presente podría dar preponderancia a algunos argumentos por sobre aquellos que los contradicen, produciendo un conjunto de conclusiones que se considera ran garantizadas. El objetivo principal de esta tesis es la definición de un nuevo marco argumentativo capaz de manejar dinámica de conocimiento. En este sentido, se da una representación no sólo a los argumentos, sino que también se introduce la noción de evidencia como entidades especiales dentro del sistema. En cada instante, el conjunto de evidencia se corresponde con la situación actual, dándole contexto al marco argumentativo. La plausibilidad de los argumentos en un instante dado depende exclusivamente de la evidencia disponible. Cuando la evidencia es suficiente para dar soporte a un argumento, éste se denominará activo. También se considera la posibilidad de que algunos argumentos se encuentren activos aun sin encontrar soporte directamente desde la evidencia, ya que podrían hacerlo a través de las conclusiones de otros argumentos activos. Estas conexiones entre argumentos dan lugar a lo que en esta tesis se denomina estructura argumental, proveyendo una visión un tanto más compleja que la usual en cuanto a la representación de conocimiento argumentativo. Los resultados obtenidos en esta tesis permitirán estudiar la dinámica de conocimiento en sistemas argumentativos. En la actualidad, ya se han publicado artáculos que presentan un formalismo que combina argumentación y la teoría clásica de revisión de creencias. En esta línea de investigación se denen operadores de cambio que se aplican sobre el marco argumentativo abstracto dinámico y tienen como objetivo alcanzar cierto estado del sistema; por ejemplo, garantizar un argumento determinado. Por otra parte, este marco también permitirá estudiar métodos para acelerar el computo de garantía a partir del proceso de razonamiento realizado en estados anteriores.

Description Logics (DLs) are increasingly successful knowledge representation formalisms, useful for any application requiring implicit derivation of knowledge from explicitly known facts. A prominent example domain benefiting from these formalisms since the 1990s is the biomedical field. This area contributes an intangible amount of facts and relations between low- and high-level concepts such as the constitution of cells or interactions between studied illnesses, their symptoms and remedies. DLs are well-suited for handling large formal knowledge repositories and computing inferable coherences throughout such data, relying on their well-founded first-order semantics. In particular, DLs of reduced expressivity have proven a tremendous worth for handling large ontologies due to their computational tractability. In spite of these assets and prevailing influence, classical DLs are not well-suited to adequately model some of the most intuitive forms of reasoning. The capability for abductive reasoning is imperative for any field subjected to incomplete knowledge and the motivation to complete it with typical expectations. When such default expectations receive contradicting evidence, an abductive formalism is able to retract previously drawn, conflicting conclusions. Common examples often include human reasoning or a default characterisation of properties in biology, such as the normal arrangement of organs in the human body. Treatment of such defeasible knowledge must be aware of exceptional cases - such as a human suffering from the congenital condition situs inversus - and therefore accommodate for the ability to retract defeasible conclusions in a non-monotonic fashion. Specifically tailored non-monotonic semantics have been continuously investigated for DLs in the past 30 years. A particularly promising approach, is rooted in the research by Kraus, Lehmann and Magidor for preferential (propositional) logics and Rational Closure (RC). The biggest advantages of RC are its well-behaviour in terms of formal inference postulates and the efficient computation of defeasible entailments, by relying on a tractable reduction to classical reasoning in the underlying formalism. A major contribution of this work is a reorganisation of the core of this reasoning method, into an abstract framework formalisation. This framework is then easily instantiated to provide the reduction method for RC in DLs as well as more advanced closure operators, such as Relevant or Lexicographic Closure. In spite of their practical aptitude, we discovered that all reduction approaches fail to provide any defeasible conclusions for elements that only occur in the relational neighbourhood of the inspected elements. More explicitly, a distinguishing advantage of DLs over propositional logic is the capability to model binary relations and describe aspects of a related concept in terms of existential and universal quantification. Previous approaches to RC (and more advanced closures) are not able to derive typical behaviour for the concepts that occur within such quantification. The main contribution of this work is to introduce stronger semantics for the lightweight DL EL_bot with the capability to infer the expected entailments, while maintaining a close relation to the reduction method. We achieve this by introducing a new kind of first-order interpretation that allocates defeasible information on its elements directly. This allows to compare the level of typicality of such interpretations in terms of defeasible information satisfied at elements in the relational neighbourhood. A typicality preference relation then provides the means to single out those sets of models with maximal typicality. Based on this notion, we introduce two types of nested rational semantics, a sceptical and a selective variant, each capable of deriving the missing entailments under RC for arbitrarily nested quantified concepts. As a proof of versatility for our new semantics, we also show that the stronger Relevant Closure, can be imbued with typical information in the successors of binary relations. An extensive investigation into the computational complexity of our new semantics shows that the sceptical nested variant comes at considerable additional effort, while the selective semantics reside in the complexity of classical reasoning in the underlying DL, which remains tractable in our case.

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. Many real-world applications, like processing electronic health records (EHRs), also contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. Our contribution consists of three main parts: Firstly, we introduce a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic ELH⊥, which is based on the minimal universal model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity. Secondly, we introduce a new temporal variant of ELH⊥ that features a convexity operator. We extend this minimal-world semantics for answering metric temporal conjunctive queries with negation over the logic and obtain similar rewritability and complexity results. Thirdly, apart from the theoretical results, we evaluate minimal-world semantics in practice by selecting patients, based their EHRs, that match given criteria.

No description available.

[pt] A lógica descritiva intuicionista iALC foi criada para modelar e raciocinar sobre o domínio de Leis baseada na Jurisprudência Kelseniana [1]. No decorrer da década anterior, essa lógica foi usada de diversas maneiras para modelar normas ou formalizar raciocínio jurídico [2, 3, 4, 5, 6, 7, 8, 9, 10]. Neste trabalho pretendemos complementar trabalhos anteriores ralizados com essa lógica ao preencher algumas lacunas encontradas enquanto trabalhando com ela. A primeira lacuna ocorre por iALC não ter um modo intuitivo de explicar raciocínio nela realizado para pessoas fora do domínio da Lógica. Ela tem um Cálculo de Sequentes (CS) [6] correto e completo (com respeito a modelos conceituais intuitionistas [3]) que tem sido menos usado que o desejado, e isso se dá em grande parte devido à maneira pouco intuitiva com que CS representa provas. Apresentamos um sistema de Dedução Natural (DN) correto e completo e com (quasi-)normalização para compensar por essa dificuldade em explicar CS para não-lógicos, especialmente os do domínio legal, essenciais para nossa pesquisa. Normalização completa não é possível devido a um tipo de derivação - tirando essa exceção, o resto do sistema gera derivações uniformes. A segunda lacuna envolve não poder lidar com raciocínio não-monotônico (RNM). Em geral, utiliza-se raciocínio monotônico, no qual, se é possível concluir algo de um conjunto de premissas, não há como acrescentar outra premissa de modo a evitar a conclusão prévia. Isso não é o caso em um julgamento legal, por exemplo, no qual lados opostos buscam convencer um juiz ou júri de consequências opostas ao adicionar premissas diferentes ao caso em questão. Propomos uma investigação de caráter exploratório em busca de uma extensão de iALC para lidar com RNM a fim de representar raciocínio jurídico em outras facetas da Lei como o processo judicial, que é não-monotônico por natureza. Apresentamos propriedades desejadas e uma possível aplicação de um sistema assim via um estudo de caso. Detalhamos mais a motivação tanto para o sistema de DN quanto a extensão de RNM, assim como as decisões tomadas ao criar cada um. / [en] The intuitionistic description logic iALC was created to model and reason over the domain of Law based on Kelsenian Jurisprudence [1]. Over the past decade, this logic has been used in several ways to either model norms or formalise legal reasoning [2, 3, 4, 5, 6, 7, 8, 9, 10]. In this work we intend to complement previous research done with this logic by filling some gaps found while working with it. The first gap occurs in iALC needing an intuitive way to explain reasoning for non-logicians. It has a sound and complete (concerning intuitionistic conceptual models [3]) Sequent Calculus (SC) [6] that has seen less usage than expected due to its non-intuitive way of presenting a proof. We present a (quasi-)normalising, sound and complete (w.r.t. TBox validity for intuitionistic conceptual models) Natural Deduction (ND) System to cover this difficulty in explaining SC to non-logicians, especially those in the domain of Law, which are essential to us. We do not achieve full normalisation due to a kind of derivation which cannot be normalised - aside from this exception, the rest of the system can provide uniform derivations. The second gap is being unable to deal with non-monotonic reasoning (NMR). Usually, one considers monotonic reasoning, in which, if one can conclude something from a set of premises, there is no way to add another premise to avoid said conclusion. This is not the case in a court of law, for instance, in which different parties aim to convince a judge or jury of opposite consequences by adding different premises to the case itself. We provide an exploratory investigation of an extension of iALC to deal with NMR to represent legal reasoning in aspects of the Law, such as the judicial process, which is non-monotonic by nature. We present desirable properties and a possible application of such a system via a case study. We explain further the motivation for both the ND system and the NMR extension and the decisions taken for both.