A probabilistic logic based on the acceptability of gambles

This article presents a probabilistic logic whose sentences can be interpreted as asserting the acceptability of gambles described in terms of an underlying logic. This probabilistic logic has a concrete syntax and a complete inference procedure, and it handles conditional as well as unconditional probabilities. It synthesizes Nilsson’s probabilistic logic and Frisch and Haddawy’s anytime inference procedure with Wilson and Moral’s logic of gambles.Two distinct semantics can be used for our probabilistic logic: (1) the measure–theoretic semantics used by the prior logics already mentioned and also by the more expressive logic of Fagin, Halpern, and Meggido and (2) a behavioral semantics. Under the measure–theoretic semantics, sentences of our probabilistic logic are interpreted as assertions about a probability distribution over interpretations of the underlying logic. Under the behavioral semantics, these sentences are interpreted only as asserting the acceptability of gambles, and this suggests different directions for generalization.     

Probabilistic stit logic and its decomposition

We define an extension of stit logic that encompasses subjective probabilities representing beliefs about simultaneous choice exertion of other agents. This semantics enables us to express that an agent sees to it that a condition obtains under a minimal chance of success. We first define the fragment of XSTIT where choice exertion is not collective. Then we add lower bounds for the probability of effects to the stit syntax, and define the semantics of the newly formed stit operator in terms of subjective probabilities concerning choice exertion of other agents. We show how the resulting probabilistic stit logic faithfully generalizes the non-probabilistic XSTIT fragment. In a second step we analyze the defined probabilistic stit logic by decomposing it into an XSTIT fragment and a purely epistemic fragment. The resulting epistemic logic for grades of believes is a weak modal logic with a neighborhood semantics combining probabilistic and modal logic theory.     

Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals

Probabilistic team semantics is a framework for logical analysis of probabilistic dependencies. Our focus is on the axiomatizability, complexity, and expressivity of probabilistic inclusion logic and its extensions. We identify a natural fragment of existential second-order logic with additive real arithmetic that captures exactly the expressivity of probabilistic inclusion logic. We furthermore relate these formalisms to linear programming, and doing so obtain PTIME data complexity for the logics. Moreover, on finite structures, we show that the full existential second-order logic with additive real arithmetic can only express NP properties. Lastly, we present a sound and complete axiomatization for probabilistic inclusion logic at the atomic level.     

On elementary logics for quantitative dependencies

We define and study logics in the framework of probabilistic team semantics and over metafinite structures. Our work is paralleled by the recent development of novel axiomatizable and tractable logics in team semantics that are closed under the Boolean negation. Our logics employ new probabilistic atoms that resemble so-called extended atoms from the team semantics literature. We also define counterparts of our logics over metafinite structures and show that all of our logics can be translated into functional fixed point logic implying a polynomial time upper bound for data complexity with respect to BSS-computations.     

Belief and probability: A general theory of probability cores

This paper considers varieties of probabilism capable of distilling paradox-free qualitative doxastic notions (e.g., full belief, expectation, and plain belief) from a notion of probability taken as a primitive. We show that core systems, collections of nested propositions expressible in the underlying algebra, can play a crucial role in these derivations. We demonstrate how the notion of a probability core can be naturally generalized to high probability, giving rise to what we call a high probability core, a notion that when formulated in terms of classical monadic probability coincides with the notion of stability proposed by Hannes Leitgeb [32]. Our work continues by one of us in collaboration with Rohit Parikh [7]. In turn, the latter work was inspired by the seminal work of Bas van Fraassen [46]. We argue that the adoption of dyadic probability as a primitive (as articulated by van Fraassen [46]) admits a smoother connection with the standard theory of probability cores as well as a better model in which to situate doxastic notions like full belief. We also illustrate how the basic structure underlying a system of cores naturally leads to alternative probabilistic acceptance rules, like the so-called ratio rule initially proposed by Isaac Levi [34].Core systems in their various guises are ubiquitous in many areas of formal epistemology (e.g., belief revision, the semantics of conditionals, modal logic, etc.). We argue that core systems can also play a natural and important role in Bayesian epistemology and decision theory. In fact, the final part of the article shows that probabilistic core systems are naturally derivable from basic decision-theoretic axioms which incorporate only qualitative aspects of core systems; that the qualitative aspects of core systems alone can be naturally integrated in the articulation of coherence of primitive conditional probability; and that the guiding idea behind the primary qualitative features of a core system gives rise to the formulation of lexicographic decision rules.     

The distribution semantics for normal programs with function symbols

The distribution semantics integrates logic programming and probability theory using a possible worlds approach. Its intuitiveness and simplicity have made it the most widely used semantics for probabilistic logic programming, with successful applications in many domains. When the program has function symbols, the semantics was defined for special cases: either the program has to be definite or the queries must have a finite number of finite explanations. In this paper we show that it is possible to define the semantics for all programs. We also show that this definition coincides with that of Sato and Kameya on positive programs. Moreover, we highlight possible approaches for inference, both exact and approximate.     

Logic of agreement: Foundations,semantic system and proof theory

In this paper a multi-valued propositional logic — logic of agreement — in terms of its model theory and inference system is presented. This formal system is the natural consequence of a new way to approach concepts as commonsense knowledge, uncertainty and approximate reasoning — the point of view of agreement. Particularly, it is discussed a possible extension of the Classical Theory of Sets based on the idea that, instead of trying to conceptualize sets as “fuzzy” or “vague” entities, it is more adequate to define membership as the result of a partial agreement among a group of individual agents. Furthermore, it is shown that the concept of agreement provides a framework for the development of a formal and sound explanation for concepts (e.g. fuzzy sets) which lack formal semantics. According to the definition of agreement, an individual agent agrees or not with the fact that an object possesses a certain property. A clear distinction is then established, between an individual agent — to whom deciding whether an element belongs to a set is just a yes or no matter — and a commonsensical agent — the one who interprets the knowledge shared by a certain group of people. Finally, the logic of agreement is presented and discussed. As it is assumed the existence of several individual agents, the semantic system is based on the perspective that each individual agent defines her/his own conceptualization of reality. So the semantics of the logic of agreement can be seen as being similar to a semantics of possible worlds, one for each individual agent. The proof theory is an extension of a natural deduction system, using supported formulas and incorporating only inference rules. Moreover, the soundness and completeness of the logic of agreement are also presented.     

Probabilization of Logics: Completeness and Decidability

The probabilization of a logic system consists of enriching the language (the formulas) and the semantics (the models) with probabilistic features. Such an operation is said to be exogenous if the enrichment is done on top, without internal changes to the structure, and is called endogenous otherwise. These two different enrichments can be applied simultaneously to the language and semantics of a same logic. We address the problem of studying the transference of metaproperties, such as completeness and decidability, to the exogenous probabilization of an abstract logic system. First, we setup the necessary framework to handle the probabilization of a satisfaction system by proving transference results within a more general context. In this setup, we define a combination mechanism of logics through morphisms and prove sufficient condition to guarantee completeness and decidability. Then, we demonstrate that probabilization is a special case of this exogenous combination method, and that it fulfills the general conditions to obtain transference of completeness and decidability. Finally, we motivate the applicability of our technique by analyzing the probabilization of the linear temporal logic over Markov chains, which constitutes an endogenous probabilization. The results are obtained first by studying the exogenous semantics, and then by establishing an equivalence with the original probabilization given by Markov chains.     

Approximate credal network updating by linear programming with applications to decision making

Credal nets are probabilistic graphical models which extend Bayesian nets to cope with sets of distributions. An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to accurate inferences. A transformation is also derived to reduce decision making in credal networks based on the maximality criterion to updating. The decision task is proved to have the same complexity of standard inference, being NP^PP-complete for general credal nets and NP-complete for polytrees. Similar results are derived for the E-admissibility criterion. Numerical experiments confirm a good performance of the method.     

Constructive agents

Brouwer’s ideas of construction, proof, and inquiry in mathematics are more widely applicable. On a well-known philosophical view, intuitionistic logic is a general account of meaning and reasoning for natural language and epistemology. In this brief discussion piece, I go one step further, and discuss how intuitionistic semantics fits with information update and belief revision in agency. In the process, I define a number of new logical systems that give rise to several open problems.     

Separation logic and logics with team semantics

Separation logic is a successful logical system for formal reasoning about programs that mutate their data structures. Team semantics, on the other side, is the basis of modern logics of dependence and independence. Separation logic and team semantics have been introduced with quite different motivations, and are investigated by research communities with rather different backgrounds and objectives. Nevertheless, there are obvious similarities between these formalisms. Both separation logic and logics with team semantics involve the manipulation of second-order objects, such as heaps and teams, by first-order syntax without reference to second-order variables. Moreover, these semantical objects are closely related; it is for instance obvious that a heap can be seen as a team, and the separating conjunction of separation logic is (essentially) the same as the team-semantical disjunction. Based on such similarities, the possible connections between separation logic and team semantics have been raised as a question at several occasions, and lead to informal discussions between these research communities. The objective of this paper is to make this connection precise, and to study its potential but also its obstacles and limitations.     

Learning failure-free PRISM programs

PRISM is a probabilistic logic programming formalism which allows defining a probability distribution over possible worlds. This paper investigates learning a class of generative PRISM programs known as failure-free. The aim is to learn recursive PRISM programs which can be used to model stochastic processes. These programs generalise dynamic Bayesian networks by defining a halting distribution over the generative process. Dynamic Bayesian networks model infinite stochastic processes. Sampling from infinite process can only be done by specifying the length of sequences that the process generates. In this case, only observations of a fixed length of sequences can be obtained. On the other hand, the recursive PRISM programs considered in this paper are self-terminating upon some halting conditions. Thus, they generate observations of different lengths of sequences. The direction taken by this paper is to combine ideas from inductive logic programming and learning Bayesian networks to learn PRISM programs. It builds upon the inductive logic programming approach of learning from entailment.     

Order-enriched categorical models of the classical sequent calculus

It is well-known that weakening and contraction cause naïve categorical models of the classical sequent calculus to collapse to Boolean lattices. Starting from a convenient formulation of the well-known categorical semantics of linear classical sequent proofs, we give models of weakening and contraction that do not collapse. Cut-reduction is interpreted by a partial order between morphisms. Our models make no commitment to any translation of classical logic into intuitionistic logic and distinguish non-deterministic choices of cut-elimination. We show soundness and completeness via initial models built from proof nets, and describe models built from sets and relations.     

Strategies and simulations in a semantic framework

By means of several examples of structural operational semantics for a variety of languages, we justify the importance and interest of using the notions of strategies and simulations in the semantic framework provided by rewriting logic and implemented in the Maude metalanguage. On the one hand, we describe a basic strategy language for Maude and show its application to CCS, the ambient calculus, and the parallel functional language Eden. On the other hand, we show how the concept of stuttering simulation can be used inside Maude to show that a stack machine correctly implements the operational semantics of a simple functional language.     

Unifying hidden-variable problems from quantum mechanics by logics of dependence and independence

We study hidden-variable models from quantum mechanics and their abstractions in purely probabilistic and relational frameworks by means of logics of dependence and independence, which are based on team semantics. We show that common desirable properties of hidden-variable models can be defined in an elegant and concise way in dependence and independence logic. The relationship between different properties and their simultaneous realisability can thus be formulated and proven on a purely logical level, as problems of entailment and satisfiability of logical formulae. Connections between probabilistic and relational entailment in dependence and independence logic allow us to simplify proofs. In many cases, we can establish results on both probabilistic and relational hidden-variable models by a single proof, because one case implies the other, depending on purely syntactic criteria. We also discuss the ‘no-go’ theorems by Bell and Kochen-Specker and provide a purely logical variant of the latter, introducing non-contextual choice as a team-semantical property.     

Mapping deontic operators to abductive expectations

Deontic concepts and operators have been widely used in several fields where representation of norms is needed, including legal reasoning and normative multi-agent systems. The EU-funded SOCS project has provided a language to specify the agent interaction in open multi-agent systems. The language is equipped with a declarative semantics based on abductive logic programming, and an operational semantics consisting of a (sound and complete) abductive proof procedure. In the SOCS framework, the specification is used directly as a program for the verification procedure. In this paper, we propose a mapping of the usual deontic operators (obligations, prohibition, permission) to language entities, called expectations, available in the SOCS social framework. Although expectations and deontic operators can be quite different from a philosophical viewpoint, we support our mapping by showing a similarity between the abductive semantics for expectations and the Kripke semantics that can be given to deontic operators. The main purpose of this work is to make the computational machinery from the SOCS social framework available for the specification and verification of systems by means of deontic operators. Marco Alberti received his laurea degree in Electronic Engineering in 2001 and his Ph.D. in Information Engineering in 2005 from the University of Ferrara, Italy. His research interests include constraint logic programming and abductive logic programming, applied in particular to the specification and verification of multi-agent systems. He has been involved as a research assistants in national and European research projects. He currently has a post-doc position in the Department of Engineering at the University of Ferrara. Marco Gavanelli is currently assistant professor in the Department of Engineering at the University of Ferrara, Italy. He graduated in Computer Science Engineering in 1998 at the University of Bologna, Italy. He got his Ph.D. in 2002 at Ferrara University. His research interest include Artificial Intelligence, Constraint Logic Programming, Multi-criteria Optimisation, Abductive Logic Programming, Multi-Agent Systems. He is a member of ALP (the Association for Logic Programming) and AI*IA (the Italian Association for Artificial Intelligence). He has organised workshops, and is author of more than 30 publications between journals and conference proceedings. Evelina Lamma received her degree in Electronic Engineering from University of Bologna, Italy, in 1985 and her Ph.D. degree in Computer Science in 1990. Currently she is Full Professor at the Faculty of Engineering of the University of Ferrara where she teaches Artificial Intelligence and Foundations of Computer Science. Her research activity focuses around: – programming languages (logic languages, modular and object-oriented programming); – artificial intelligence; – knowledge representation; – intelligent agents and multi-agent systems; – machine learning. Her research has covered implementation, application and theoretical aspects. She took part to several national and international research projects. She was responsible of the research group at the Dipartimento di Ingegneria of the University of Ferrara in the UE ITS-2001-32530 Project (named SOCS), in the the context of the UE V Framework Programme - Global Computing Action. Paola Mello received her degree in Electronic Engineering from the University of Bologna, Italy, in 1982, and her Ph.D. degree in Computer Science in 1989. Since 1994 she has been Full Professor. She is enrolled, at present, at the Faculty of Engineering of the University of Bologna (Italy), where she teaches Artificial Intelligence. Her research activity focuses on programming languages, with particular reference to logic languages and their extensions, artificial intelligence, knowledge representation, expert systems with particular emphasis on medical applications, and multi-agent systems. Her research has covered implementation, application and theoretical aspects and is presented in several national and international publications. She took part to several national and international research projects in the context of computational logic. Giovanni Sartor is Marie-Curie professor of Legal informatics and Legal Theory at the European University Institute of Florence and professor of Computer and Law at the University of Bologna (on leave), after obtaining a PhD at the European University Institute (Florence), working at the Court of Justice of the European Union (Luxembourg), being a researcher at the Italian National Council of Research (ITTIG, Florence), and holding the chair in Jurisprudence at Queen’s University of Belfast (where he now is honorary professor). He is co-editor of the Artificial Intelligence and Law Journal and has published widely in legal philosophy, computational logic, legislation technique, and computer law. Paolo Torroni is Assistant Professor in computing at the Faculty of Engineering of the University of Bologna, Italy. He obtained a PhD in Computer Science and Electronic Engineering in 2002, with a dissertation on logic-based agent reasoning and interaction. His research interests mainly focus on computational logic and multi-agent systems research, including logic programming, abductive and hypothetical reasoning, agent interaction, dialogue, negotiation, and argumentation. He is in the steering committee of the CLIMA and DALT international workshops and of the Italian logic programming interest group GULP.     

On the equivalence between logic programming semantics and argumentation semantics

In the current paper, we re-examine the connection between formal argumentation and logic programming from the perspective of semantics. We observe that one particular translation from logic programs to instantiated argumentation (the one described by Wu, Caminada and Gabbay) is able to serve as a basis for describing various equivalences between logic programming semantics and argumentation semantics. In particular, we are able to show equivalence between regular semantics for logic programming and preferred semantics for formal argumentation. We also show that there exist logic programming semantics (L-stable semantics) that cannot be captured by any abstract argumentation semantics.     

Compositional Meaning in Logic

The Fregean-inspired Principle of Compositionality of Meaning (PoC) for formal languages asserts that the meaning of a compound expression is analysable in terms of the meaning of its constituents, taking into account the mode in which these constituents are combined so as to form the compound expression. From a logical point of view, this amounts to prescribing a constraint—that may or may not be respected—on the internal mechanisms that build and give meaning to a given formal system. Within the domain of formal semantics and of the structure of logical derivations, the PoC is often directly reflected by metaproperties such as truth-functionality and analyticity, characteristic of computationally well-behaved logical systems.     

Computational complexity of hybrid interval temporal logics

Interval logics are very expressive temporal formalisms, but reasoning with them is often undecidable or has high computational complexity. As a result, a vast number of approaches limiting their expressive power—in order to obtain better computational behaviour—have been introduced. Unfortunately, due to such restrictions, interval logics often lose referentiality, that is, the capacity to refer to specific time intervals, which is crucial for temporal representation and reasoning. The computational price that needs to be paid in order to regain referentiality is not well studied and our research aims to fill this gap. In particular we study the main interval temporal logic, called the Halpern-Shoham logic, and its low complexity modifications. To regain referentiality in these modifications, we extend the language with the hybrid machinery—nominals and satisfaction operators—and classify the obtained logics according to their computational complexity. We show that such a hybridisation often makes tractable logics intractable but not undecidable. This allows us to construct hybrid interval temporal logics which are referential as well as maintain a good compromise between expressiveness and complexity; it makes them valuable formalisms for temporal knowledge representation. We also introduce a class of models which, due to a specific interplay between the interpretation of modal operators and a structure of time, makes reasoning in interval logics computationally hard even in the absence of the hybrid machinery.