Models of true concurrency have gained a lot of interest over the last decades as models of concurrent or distributed systems which avoid the well-known problem of state space explosion of the interleaving models. In this thesis, we study such models from two perspectives. Firstly, we study the relation between Petri nets and stable event structures. Petri nets can be considered as one of the most general and perhaps wide-spread models of true concurrency. Event structures on the other hand, are simpler models of true concurrency with explicit causality and conflict relations. Stable event structures expand the class of event structures by allowing events to be enabled in more than one way. While the relation between Petri nets and event structures is well understood, the relation between Petri nets and stable event structures has not been studied explicitly. We define a new and more compact unfoldings of safe Petri nets which is directly translatable to stable event structures. In addition, the notion of complete finite prefix is defined for compact unfoldings, making the existing model checking algorithms applicable to them. We present algorithms for constructing the compact unfoldings and their complete finite prefix. Secondly, we study probabilistic models of true concurrency. We extend the definition of probabilistic event structures as defined by Abbes and Benveniste to a newly defined class of stable event structures, namely, jump-free stable event structures arising from Petri nets (characterised and referred to as net-driven). This requires defining the fundamental concept of branching cells in probabilistic event structures, for jump-free net-driven stable event structures, and by proving the existence of an isomorphism among the branching cells of these systems, we show that the latter benefit from the related results of the former models. We then move on to defining a probabilistic logic over probabilistic event structures (PESL). To our best knowledge, this is the first probabilistic logic of true concurrency. We show examples of expressivity achieved by PESL, which in particular include properties related to synchronisation in the system. This is followed by the model checking algorithm for PESL for finite event structures. Finally, we present a logic over stable event structures (SEL) along with an account of its expressivity and its model checking algorithm for finite stable event structures.

A busca por explicações de fatos ou fenômenos é algo que sempre permeou o raciocínio humano. Desde a antiguidade, o ser humano costuma observar fatos e, de acordo com eles e o conhecimento presente, criar hipóteses que possam explicá-los. Um exemplo clássico é quando temos consulta médica e o médico, após verificar todos os sintomas, descobre qual é a doença e os meios de tratá-la. Essa construção de explicações, dado um conjunto de evidências que o indiquem, chamamos de \\textit{abdução}. A abdução tradicional para a lógica clássica estabelece que o dado meta não é derivado da base de conhecimento, ou seja, dada uma base de conhecimento $\\Gamma$ e um dado meta $A$ temos $\\Gamma ot \\vdash A$. Métodos clássicos de abdução buscam gerar um novo dado $H$ que, juntamente com uma base de conhecimento $\\Gamma$, possamos inferir $A$ ($\\Gamma \\cup H \\vdash A$). Alguns métodos tradicionais utilizam o tableaux (como em \\cite) para a geração da fórmula $H$. Aqui, além de lidarmos com a abdução baseada em corte, através do KE-tableaux, que não necessita assumir que o dado meta não seja derivado da base de conhecimento, lidaremos também com a lógica probabilística, redescoberta por Nilsson, em \\cite, onde temos a atribuição de probabilidades a fórmulas. Dizemos que uma instância em lógica probabilística é consistente se existe uma distribuição probabilística consistente sobre as valorações. Determinar essa distribuição probabilística é que o chamamos de problema PSAT. O objetivo de nosso trabalho é definir e estabelecer o que é uma abdução em Lógica Probabilística (abdução em PSAT) e, além disso, fornecer métodos de abdução para PSAT: dada uma instância PSAT $\\left\\langle \\Gamma, \\Psi ightangle$ na forma normal atômica \\cite e uma fórmula $A$ tal que existe uma distribuição probabi bylística $\\pi$ que satisfaz $\\left\\langle \\Gamma, \\Psi ightangle$ e $\\pi(A) = 0$, cada método é capaz de gerar uma fórmula $H$ tal que $\\left\\langle \\Gamma \\cup H , \\Psi ightangle \\!\\!|\\!\\!\\!\\approx A$ onde $\\pi(A) > 0$ para toda distribuição $\\pi$ que satisfaça $\\left\\langle \\Gamma \\cup H , \\Psi ightangle$. Iremos também demonstrar que alguns dos métodos apresentados são corretos e completos na geração de fórmulas $H$ que satisfaçam as condições de abdução. / The search for explanations of facts or phenomena is something that has always permeated human reasoning. Since antiquity, the human being usually observes facts and, according to them and his knowledge, create hypotheses that can explain them. A classic example is when we have medical consultation and the doctor, after checking all the symptoms, discovers what is the disease and the ways to treat it. This construction of explanations, given a set of evidence, we call \\textit. In traditional abduction methods it is assumed that the goal data has not yet been explained, that is, given a background knowledge base $\\Gamma$ and a goal data $A$ we have $\\Gamma ot \\vdash A$. Classical methods want to generate a new datum $H$ in such way that with the background knowledge base $\\Gamma$, we can infer $A$ ($\\Gamma \\cup H \\vdash A$). Some traditional methods use the analytical tableaux (see \\cite) for the generation of $H$. Here we deal with a cut-based abduction, with the KE-tableaux, which do not need to assume that the goal data is not derived from the knowledge base, and, moreover, with probabilistic logic (PSAT), rediscovered in \\cite, where we have probabilistic assignments to logical formulas. A PSAT instance is consistent if there is a probabilistic distribution over the assignments. The aim of our work is to define and establish what is an abduction in Probabilistic Logic (abduction for PSAT) and, moreover, provide methods for PSAT abduction: given a PSAT instance $\\left\\langle \\Gamma, \\Psi ightangle$ in atomic normal form \\cite and a formula $A$ such that there is a probabilistic distribution $\\pi$ that satisfies $\\left\\langle \\Gamma, \\Psi ightangle$ and $\\pi(A)=0$, each method is able to generate a formula $H$ such that $\\left\\langle \\Gamma \\cup H , \\Psi ightangle \\!\\!|\\!\\!\\!\\approx A$ where $\\pi(A) > 0$ for all distribution $\\pi$ that satisfies $\\left\\langle \\Gamma \\cup H , \\Psi ightangle$. We demonstrated that some of the our methods, shown in this work, are correct and complete for the generation of $H$.

To learn a probabilistic logic program is to find a set of probabilistic rules that best fits some data, in order to explain how attributes relate to one another and to predict the occurrence of new instantiations of these attributes. In this work, we focus on acyclic programs, because in this case the meaning of the program is quite transparent and easy to grasp. We propose that the learning process for a probabilistic acyclic logic program should be guided by a scoring function imported from the literature on Bayesian network learning. We suggest novel techniques that lead to orders of magnitude improvements in the current state-of-art represented by the ProbLog package. In addition, we present novel techniques for learning the structure of acyclic probabilistic logic programs. / O aprendizado de um programa lógico probabilístico consiste em encontrar um conjunto de regras lógico-probabilísticas que melhor se adequem aos dados, a fim de explicar de que forma estão relacionados os atributos observados e predizer a ocorrência de novas instanciações destes atributos. Neste trabalho focamos em programas acíclicos, cujo significado é bastante claro e fácil de interpretar. Propõe-se que o processo de aprendizado de programas lógicos probabilísticos acíclicos deve ser guiado por funções de avaliação importadas da literatura de aprendizado de redes Bayesianas. Neste trabalho s~ao sugeridas novas técnicas para aprendizado de parâmetros que contribuem para uma melhora significativa na eficiência computacional do estado da arte representado pelo pacote ProbLog. Além disto, apresentamos novas técnicas para aprendizado da estrutura de programas lógicos probabilísticos acíclicos.

In terms of standard probabilistic reasoning, in order to perform inference from a knowledge base, it is normally necessary to guarantee the consistency of such base. When we come across an inconsistent set of probabilistic assessments, it interests us to know where the inconsistency is, how severe it is, and how to correct it. Inconsistency measures have recently been put forward as a tool to address these issues in the Artificial Intelligence community. This work investigates the problem of measuring inconsistency in probabilistic knowledge bases. Basic rationality postulates have driven the formulation of inconsistency measures within classical propositional logic. In the probabilistic case, the quantitative character of probabilities yielded an extra desirable property: that inconsistency measures should be continuous. To attend this requirement, inconsistency in probabilistic knowledge bases have been measured via distance minimisation. In this thesis, we prove that the continuity postulate is incompatible with basic desirable properties inherited from classical logic. Since minimal inconsistent sets are the basis for some desiderata, we look for more suitable ways of localising the inconsistency in probabilistic logic, while we analyse the underlying consolidation processes. The AGM theory of belief revision is extended to encompass consolidation via probabilities adjustment. The new forms of characterising the inconsistency we propose are employed to weaken some postulates, restoring the compatibility of the whole set of desirable properties. Investigations in Bayesian statistics and formal epistemology have been interested in measuring an agent\'s degree of incoherence. In these fields, probabilities are usually construed as an agent\'s degrees of belief, determining her gambling behaviour. Incoherent agents hold inconsistent degrees of beliefs, which expose them to disadvantageous bet transactions - also known as Dutch books. Statisticians and philosophers suggest measuring an agent\'s incoherence through the guaranteed loss she is vulnerable to. We prove that these incoherence measures via Dutch book are equivalent to inconsistency measures via distance minimisation from the AI community. / Em termos de raciocínio probabilístico clássico, para se realizar inferências de uma base de conhecimento, normalmente é necessário garantir a consistência de tal base. Quando nos deparamos com um conjunto de probabilidades que são inconsistentes entre si, interessa-nos saber onde está a inconsistência, quão grave esta é, e como corrigi-la. Medidas de inconsistência têm sido recentemente propostas como uma ferramenta para endereçar essas questões na comunidade de Inteligência Artificial. Este trabalho investiga o problema da medição de inconsistência em bases de conhecimento probabilístico. Postulados básicos de racionalidade têm guiado a formulação de medidas de inconsistência na lógica clássica proposicional. No caso probabilístico, o carácter quantitativo da probabilidade levou a uma propriedade desejável adicional: medidas de inconsistência devem ser contínuas. Para atender a essa exigência, a inconsistência em bases de conhecimento probabilístico tem sido medida através da minimização de distâncias. Nesta tese, demonstramos que o postulado da continuidade é incompatível com propriedades desejáveis herdadas da lógica clássica. Como algumas dessas propriedades são baseadas em conjuntos inconsistentes minimais, nós procuramos por maneiras mais adequadas de localizar a inconsistência em lógica probabilística, analisando os processos de consolidação subjacentes. A teoria AGM de revisão de crenças é estendida para englobar a consolidação pelo ajuste de probabilidades. As novas formas de caracterizar a inconsistência que propomos são empregadas para enfraquecer alguns postulados, restaurando a compatibilidade de todo o conjunto de propriedades desejáveis. Investigações em estatística Bayesiana e em epistemologia formal têm se interessado pela medição do grau de incoerência de um agente. Nesses campos, probabilidades são geralmente interpretadas como graus de crença de um agente, determinando seu comportamento em apostas. Agentes incoerentes possuem graus de crença inconsistentes, que o expõem a transações de apostas desvantajosas - conhecidas como Dutch books. Estatísticos e filósofos sugerem medir a incoerência de um agente através do prejuízo garantido a qual ele está vulnerável. Nós provamos que estas medidas de incoerência via Dutch books são equivalentes a medidas de inconsistência via minimização de distâncias da comunidade de IA.

To learn a probabilistic logic program is to find a set of probabilistic rules that best fits some data, in order to explain how attributes relate to one another and to predict the occurrence of new instantiations of these attributes. In this work, we focus on acyclic programs, because in this case the meaning of the program is quite transparent and easy to grasp. We propose that the learning process for a probabilistic acyclic logic program should be guided by a scoring function imported from the literature on Bayesian network learning. We suggest novel techniques that lead to orders of magnitude improvements in the current state-of-art represented by the ProbLog package. In addition, we present novel techniques for learning the structure of acyclic probabilistic logic programs. / O aprendizado de um programa lógico probabilístico consiste em encontrar um conjunto de regras lógico-probabilísticas que melhor se adequem aos dados, a fim de explicar de que forma estão relacionados os atributos observados e predizer a ocorrência de novas instanciações destes atributos. Neste trabalho focamos em programas acíclicos, cujo significado é bastante claro e fácil de interpretar. Propõe-se que o processo de aprendizado de programas lógicos probabilísticos acíclicos deve ser guiado por funções de avaliação importadas da literatura de aprendizado de redes Bayesianas. Neste trabalho s~ao sugeridas novas técnicas para aprendizado de parâmetros que contribuem para uma melhora significativa na eficiência computacional do estado da arte representado pelo pacote ProbLog. Além disto, apresentamos novas técnicas para aprendizado da estrutura de programas lógicos probabilísticos acíclicos.

In terms of standard probabilistic reasoning, in order to perform inference from a knowledge base, it is normally necessary to guarantee the consistency of such base. When we come across an inconsistent set of probabilistic assessments, it interests us to know where the inconsistency is, how severe it is, and how to correct it. Inconsistency measures have recently been put forward as a tool to address these issues in the Artificial Intelligence community. This work investigates the problem of measuring inconsistency in probabilistic knowledge bases. Basic rationality postulates have driven the formulation of inconsistency measures within classical propositional logic. In the probabilistic case, the quantitative character of probabilities yielded an extra desirable property: that inconsistency measures should be continuous. To attend this requirement, inconsistency in probabilistic knowledge bases have been measured via distance minimisation. In this thesis, we prove that the continuity postulate is incompatible with basic desirable properties inherited from classical logic. Since minimal inconsistent sets are the basis for some desiderata, we look for more suitable ways of localising the inconsistency in probabilistic logic, while we analyse the underlying consolidation processes. The AGM theory of belief revision is extended to encompass consolidation via probabilities adjustment. The new forms of characterising the inconsistency we propose are employed to weaken some postulates, restoring the compatibility of the whole set of desirable properties. Investigations in Bayesian statistics and formal epistemology have been interested in measuring an agent\'s degree of incoherence. In these fields, probabilities are usually construed as an agent\'s degrees of belief, determining her gambling behaviour. Incoherent agents hold inconsistent degrees of beliefs, which expose them to disadvantageous bet transactions - also known as Dutch books. Statisticians and philosophers suggest measuring an agent\'s incoherence through the guaranteed loss she is vulnerable to. We prove that these incoherence measures via Dutch book are equivalent to inconsistency measures via distance minimisation from the AI community. / Em termos de raciocínio probabilístico clássico, para se realizar inferências de uma base de conhecimento, normalmente é necessário garantir a consistência de tal base. Quando nos deparamos com um conjunto de probabilidades que são inconsistentes entre si, interessa-nos saber onde está a inconsistência, quão grave esta é, e como corrigi-la. Medidas de inconsistência têm sido recentemente propostas como uma ferramenta para endereçar essas questões na comunidade de Inteligência Artificial. Este trabalho investiga o problema da medição de inconsistência em bases de conhecimento probabilístico. Postulados básicos de racionalidade têm guiado a formulação de medidas de inconsistência na lógica clássica proposicional. No caso probabilístico, o carácter quantitativo da probabilidade levou a uma propriedade desejável adicional: medidas de inconsistência devem ser contínuas. Para atender a essa exigência, a inconsistência em bases de conhecimento probabilístico tem sido medida através da minimização de distâncias. Nesta tese, demonstramos que o postulado da continuidade é incompatível com propriedades desejáveis herdadas da lógica clássica. Como algumas dessas propriedades são baseadas em conjuntos inconsistentes minimais, nós procuramos por maneiras mais adequadas de localizar a inconsistência em lógica probabilística, analisando os processos de consolidação subjacentes. A teoria AGM de revisão de crenças é estendida para englobar a consolidação pelo ajuste de probabilidades. As novas formas de caracterizar a inconsistência que propomos são empregadas para enfraquecer alguns postulados, restaurando a compatibilidade de todo o conjunto de propriedades desejáveis. Investigações em estatística Bayesiana e em epistemologia formal têm se interessado pela medição do grau de incoerência de um agente. Nesses campos, probabilidades são geralmente interpretadas como graus de crença de um agente, determinando seu comportamento em apostas. Agentes incoerentes possuem graus de crença inconsistentes, que o expõem a transações de apostas desvantajosas - conhecidas como Dutch books. Estatísticos e filósofos sugerem medir a incoerência de um agente através do prejuízo garantido a qual ele está vulnerável. Nós provamos que estas medidas de incoerência via Dutch books são equivalentes a medidas de inconsistência via minimização de distâncias da comunidade de IA.

A busca por explicações de fatos ou fenômenos é algo que sempre permeou o raciocínio humano. Desde a antiguidade, o ser humano costuma observar fatos e, de acordo com eles e o conhecimento presente, criar hipóteses que possam explicá-los. Um exemplo clássico é quando temos consulta médica e o médico, após verificar todos os sintomas, descobre qual é a doença e os meios de tratá-la. Essa construção de explicações, dado um conjunto de evidências que o indiquem, chamamos de \\textit{abdução}. A abdução tradicional para a lógica clássica estabelece que o dado meta não é derivado da base de conhecimento, ou seja, dada uma base de conhecimento $\\Gamma$ e um dado meta $A$ temos $\\Gamma ot \\vdash A$. Métodos clássicos de abdução buscam gerar um novo dado $H$ que, juntamente com uma base de conhecimento $\\Gamma$, possamos inferir $A$ ($\\Gamma \\cup H \\vdash A$). Alguns métodos tradicionais utilizam o tableaux (como em \\cite) para a geração da fórmula $H$. Aqui, além de lidarmos com a abdução baseada em corte, através do KE-tableaux, que não necessita assumir que o dado meta não seja derivado da base de conhecimento, lidaremos também com a lógica probabilística, redescoberta por Nilsson, em \\cite, onde temos a atribuição de probabilidades a fórmulas. Dizemos que uma instância em lógica probabilística é consistente se existe uma distribuição probabilística consistente sobre as valorações. Determinar essa distribuição probabilística é que o chamamos de problema PSAT. O objetivo de nosso trabalho é definir e estabelecer o que é uma abdução em Lógica Probabilística (abdução em PSAT) e, além disso, fornecer métodos de abdução para PSAT: dada uma instância PSAT $\\left\\langle \\Gamma, \\Psi ightangle$ na forma normal atômica \\cite e uma fórmula $A$ tal que existe uma distribuição probabi bylística $\\pi$ que satisfaz $\\left\\langle \\Gamma, \\Psi ightangle$ e $\\pi(A) = 0$, cada método é capaz de gerar uma fórmula $H$ tal que $\\left\\langle \\Gamma \\cup H , \\Psi ightangle \\!\\!|\\!\\!\\!\\approx A$ onde $\\pi(A) > 0$ para toda distribuição $\\pi$ que satisfaça $\\left\\langle \\Gamma \\cup H , \\Psi ightangle$. Iremos também demonstrar que alguns dos métodos apresentados são corretos e completos na geração de fórmulas $H$ que satisfaçam as condições de abdução. / The search for explanations of facts or phenomena is something that has always permeated human reasoning. Since antiquity, the human being usually observes facts and, according to them and his knowledge, create hypotheses that can explain them. A classic example is when we have medical consultation and the doctor, after checking all the symptoms, discovers what is the disease and the ways to treat it. This construction of explanations, given a set of evidence, we call \\textit. In traditional abduction methods it is assumed that the goal data has not yet been explained, that is, given a background knowledge base $\\Gamma$ and a goal data $A$ we have $\\Gamma ot \\vdash A$. Classical methods want to generate a new datum $H$ in such way that with the background knowledge base $\\Gamma$, we can infer $A$ ($\\Gamma \\cup H \\vdash A$). Some traditional methods use the analytical tableaux (see \\cite) for the generation of $H$. Here we deal with a cut-based abduction, with the KE-tableaux, which do not need to assume that the goal data is not derived from the knowledge base, and, moreover, with probabilistic logic (PSAT), rediscovered in \\cite, where we have probabilistic assignments to logical formulas. A PSAT instance is consistent if there is a probabilistic distribution over the assignments. The aim of our work is to define and establish what is an abduction in Probabilistic Logic (abduction for PSAT) and, moreover, provide methods for PSAT abduction: given a PSAT instance $\\left\\langle \\Gamma, \\Psi ightangle$ in atomic normal form \\cite and a formula $A$ such that there is a probabilistic distribution $\\pi$ that satisfies $\\left\\langle \\Gamma, \\Psi ightangle$ and $\\pi(A)=0$, each method is able to generate a formula $H$ such that $\\left\\langle \\Gamma \\cup H , \\Psi ightangle \\!\\!|\\!\\!\\!\\approx A$ where $\\pi(A) > 0$ for all distribution $\\pi$ that satisfies $\\left\\langle \\Gamma \\cup H , \\Psi ightangle$. We demonstrated that some of the our methods, shown in this work, are correct and complete for the generation of $H$.

In this thesis we present a framework for automatic formal analysis of competitive stochastic systems, such as sensor networks, decentralised resource management schemes or distributed user-centric environments. We model such systems as stochastic multi-player games, which are turn-based models where an action in each state is chosen by one of the players or according to a probability distribution. The specifications, such as “sensors 1 and 2 can collaborate to detect the target with probability 1, no matter what other sensors in the network do” or “the controller can ensure that the energy used is less than 75 mJ, and the algorithm terminates with probability at least 0.5'', are provided as temporal logic formulae. We introduce a branching-time temporal logic rPATL and its multi-objective extension to specify such probabilistic and reward-based properties of stochastic multi-player games. We also provide algorithms for these logics that can either verify such properties against the model, providing a yes/no answer, or perform strategy synthesis by constructing the strategy for the players that satisfies the specification. We conduct a detailed complexity analysis of the model checking problem for rPATL and its multi-objective extension and provide efficient algorithms for verification and strategy synthesis. We also implement the proposed techniques in the PRISM-games tool and apply them to the analysis of several case studies of competitive stochastic systems.

O problema da Satisfazibilidade Probabilística, PSAT, apesar da sua flexibilidade, torna exponencialmente complexa a modelagem de variáveis estatisticamente independentes. Esta tese busca desenvolver algoritmos e propostas de relaxamento para permitir o tratamento eficiente de independência parcial pelo PSAT. Apresentamos uma aplicação do PSAT ao problema da etiquetagem morfossintática que serve tanto de motivação como de demonstração dos conceitos apresentados. / The Probabilistic Satisfiability Problem, PSAT, despite its flexibility, makes it exponentially complicated to model statistically independent variables. This thesis develops algorithms and relaxation proposals that allow an efficient treatment of partial independence with PSAT. We also present an application of PSAT on the Part-of-speech tagging problem to serve both as motivation and showcase of the presented concepts.

A combinação de lógica e probabilidade (lógicas probabilísticas) tem sido um tópico bastante estudado nas últimas décadas. A maioria de propostas para estes formalismos pressupõem que tanto as sentenças lógicas como as probabilidades sejam especificadas por especialistas. Entretanto, a crescente disponibilidade de dados relacionais sugere o uso de técnicas de aprendizado de máquina para produzir sentenças lógicas e estimar probabilidades. Este trabalho apresenta contribuições em termos de representação de conhecimento e aprendizado. Primeiro, uma linguagem lógica probabilística de primeira ordem é proposta. Em seguida, três algoritmos de aprendizado de lógica de descrição probabilística crALC são apresentados: um algoritmo probabilístico com ênfase na indução de sentenças baseada em classificadores Noisy-OR; um algoritmo que foca na indução de inclusões probabilísticas (componente probabilístico de crALC); um algoritmo de natureza probabilística que induz sentenças lógicas ou inclusões probabilísticas. As propostas de aprendizado são avaliadas em termos de acurácia em duas tarefas: no aprendizado de lógicas de descrição e no aprendizado de terminologias probabilísticas em crALC. Adicionalmente, são discutidas aplicações destes algoritmos em processos de recuperação de informação: duas abordagens para extensão semântica de consultas na Web usando ontologias probabilísticas são discutidas. / The combination of logic and probabilities (probabilistic logics) is a topic that has been extensively explored in past decades. The majority of work in probabilistic logics assumes that both logical sentences and probabilities are specified by experts. As relational data is increasingly available, machine learning algorithms have been used to induce both logical sentences and probabilities. This work contributes in knowledge representation and learning. First, a rst-order probabilistic logic is proposed. Then, three algorithms for learning probabilistic description logic crALC are given: a probabilistic algorithm focused on learning logical sentences and based on Noisy-OR classiers; an algorithm that aims at learning probabilistic inclusions (probabilistic component of crALC) and; an algorithm that using a probabilistic setting, induces either logical sentences or probabilistic inclusions. Evaluation of these proposals has been performed in two situations: by measuring learning accuracy of both description logics and probabilistic terminologies. In addition, these learning algorithms have been applied to information retrieval processes: two approaches for semantic query extension through probabilistic ontologies are discussed.