The logic of justified belief,explicit knowledge,and conclusive evidence

We present a complete, decidable logic for reasoning about a notion of completely trustworthy (“conclusive”) evidence and its relations to justifiable (implicit) belief and knowledge, as well as to their explicit justifications. This logic makes use of a number of evidence-related notions such as availability, admissibility, and “goodness” of a piece of evidence, and is based on an innovative modification of the Fitting semantics for Artemov?s Justification Logic designed to preempt Gettier-type counterexamples. We combine this with ideas from belief revision and awareness logics to provide an account for explicitly justified (defeasible) knowledge based on conclusive evidence that addresses the problem of (logical) omniscience.     

Equilibrium semantics of languages of imperfect information

In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu (1989) [9] under the header of independence-friendly (IF) languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich (1986) [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics.     

Logical omniscience as infeasibility

Logical theories for representing knowledge are often plagued by the so-called Logical Omniscience Problem. The problem stems from the clash between the desire to model rational agents, which should be capable of simple logical inferences, and the fact that any logical inference, however complex, almost inevitably consists of inference steps that are simple enough. This contradiction points to the fruitlessness of trying to solve the Logical Omniscience Problem qualitatively if the rationality of agents is to be maintained. We provide a quantitative solution to the problem compatible with the two important facets of the reasoning agent: rationality and resource boundedness. More precisely, we provide a test for the logical omniscience problem in a given formal theory of knowledge. The quantitative measures we use are inspired by the complexity theory. We illustrate our framework with a number of examples ranging from the traditional implicit representation of knowledge in modal logic to the language of justification logic, which is capable of spelling out the internal inference process. We use these examples to divide representations of knowledge into logically omniscient and not logically omniscient, thus trying to determine how much information about the reasoning process needs to be present in a theory to avoid logical omniscience.     

How behaviors spread in dynamic social networks

In this paper, we explore how decentralized local interactions of autonomous agents in a network relate to collective behaviors. Earlier work in this area has modeled social networks with fixed agent relations. We instead focus on dynamic social networks in which agents can rationally adjust their neighborhoods based on their individual interests. We propose a new connection evaluation theory, the Highest Weighted Reward (HWR) rule: agents dynamically choose their neighbors in order to maximize their own utilities based on rewards from previous interactions. We prove that, in the two-action pure coordination game, our system would stabilize to a clustering state in which all relationships in the network are rewarded with an optimal payoff. Our experiments verify this theory and also reveal additional interesting patterns in the network.     

A modal logic framework for reasoning about comparative distances and topology

We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s S4 for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can be captured by one binary operator comparing distances between sets and one unary operator distinguishing between realised and limit distances (i.e., between minimum and infimum). Due to its greater expressive power, this logic turns out to behave quite differently from both S4 and conditional logics. We provide finite (Hilbert-style) axiomatisations and ExpTime-completeness proofs for the logics of various classes of distance spaces, in particular metric spaces. But we also show that the logic of the real line (and various other important metric spaces) is not recursively enumerable. This result is proved by an encoding of Diophantine equations.     

Visible acyclic differential nets, Part I: Semantics

We give a geometric condition that characterizes the differential nets having a finitary interpretation in finiteness spaces: visible acyclicity. This is based on visible paths, an extension to differential nets of a class of paths we introduced in the framework of linear logic nets. The characterization is then carried out as follows: the differential nets having no visible cycles are exactly those whose interpretation is a finitary relation. Visible acyclicity discloses a new kind of correctness for the promotion rule of linear logic, which goes beyond sequent calculus correctness.     

Lambek vs. Lambek: Functorial vector space semantics and string diagrams for Lambek calculus

The Distributional Compositional Categorical (DisCoCat) model is a mathematical framework that provides compositional semantics for meanings of natural language sentences. It consists of a computational procedure for constructing meanings of sentences, given their grammatical structure in terms of compositional type-logic, and given the empirically derived meanings of their words. For the particular case that the meaning of words is modelled within a distributional vector space model, its experimental predictions, derived from real large scale data, have outperformed other empirically validated methods that could build vectors for a full sentence. This success can be attributed to a conceptually motivated mathematical underpinning, something which the other methods lack, by integrating qualitative compositional type-logic and quantitative modelling of meaning within a category-theoretic mathematical framework. The type-logic used in the DisCoCat model is Lambek?s pregroup grammar. Pregroup types form a posetal compact closed category, which can be passed, in a functorial manner, on to the compact closed structure of vector spaces, linear maps and tensor product. The diagrammatic versions of the equational reasoning in compact closed categories can be interpreted as the flow of word meanings within sentences. Pregroups simplify Lambek?s previous type-logic, the Lambek calculus. The latter and its extensions have been extensively used to formalise and reason about various linguistic phenomena. Hence, the apparent reliance of the DisCoCat on pregroups has been seen as a shortcoming. This paper addresses this concern, by pointing out that one may as well realise a functorial passage from the original type-logic of Lambek, a monoidal bi-closed category, to vector spaces, or to any other model of meaning organised within a monoidal bi-closed category. The corresponding string diagram calculus, due to Baez and Stay, now depicts the flow of word meanings, and also reflects the structure of the parse trees of the Lambek calculus.     

Reducing belief simpliciter to degrees of belief

Is it possible to give an explicit definition of belief (simpliciter) in terms of subjective probability, such that believed propositions are guaranteed to have a sufficiently high probability, and yet it is neither the case that belief is stripped of any of its usual logical properties, nor is it the case that believed propositions are bound to have probability 1? We prove the answer is ‘yes’, and that given some plausible logical postulates on belief that involve a contextual “cautiousness” threshold, there is but one way of determining the extension of the concept of belief that does the job. The qualitative concept of belief is not to be eliminated from scientific or philosophical discourse, rather, by reducing qualitative belief to assignments of resiliently high degrees of belief and a “cautiousness” threshold, qualitative and quantitative belief turn out to be governed by one unified theory that offers the prospects of a huge range of applications. Within that theory, logic and probability theory are not opposed to each other but go hand in hand.     

What is a Logic Translation?

We study logic translations from an abstract perspective, without any commitment to the structure of sentences and the nature of logical entailment, which also means that we cover both proof- theoretic and model-theoretic entailment. We show how logic translations induce notions of logical expressiveness, consistency strength and sublogic, leading to an explanation of paradoxes that have been described in the literature. Connectives and quantifiers, although not present in the definition of logic and logic translation, can be recovered by their abstract properties and are preserved and reflected by translations under suitable conditions. In memoriam Joseph Goguen     

Bayesian MAP model selection of chain event graphs

Chain event graphs are graphical models that while retaining most of the structural advantages of Bayesian networks for model interrogation, propagation and learning, more naturally encode asymmetric state spaces and the order in which events happen than Bayesian networks do. In addition, the class of models that can be represented by chain event graphs for a finite set of discrete variables is a strict superset of the class that can be described by Bayesian networks. In this paper we demonstrate how with complete sampling, conjugate closed form model selection based on product Dirichlet priors is possible, and prove that suitable homogeneity assumptions characterise the product Dirichlet prior on this class of models. We demonstrate our techniques using two educational examples.     

The Logic of Uncertain Justifications

In Artemov?s Justification Logic, one can make statements interpreted as “t is evidence for the truth of formula F.” We propose a variant of this logic in which one can say “I have degree r of confidence that t is evidence for the truth of formula F.” After defining both an axiomatic approach and a semantics for this Logic of Uncertain Justifications, we will prove the usual soundness and completeness theorems.     

Characterizing Valiant's algebraic complexity classes

Valiant introduced 20 years ago an algebraic complexity theory to study the complexity of polynomial families. The basic computation model used is the arithmetic circuit, which makes these classes very easy to define and open to combinatorial techniques. In this paper we gather known results and new techniques under a unifying theme, namely the restrictions imposed upon the gates of the circuit, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and _VNPe${\mathrm{VNP}}_{\mathrm{e}}$ or the completeness of the Determinant for VQP, and new results such as a characterization of the classes VQP and VP (which we can also apply to the Boolean class LOGCFL) or a full answer to a conjecture in Bürgisser's book [Completeness and reduction in algebraic complexity theory, Algorithms and Computation in Mathematics, vol. 7, Springer, Berlin, 2000]. We also show that for circuits of polynomial depth and unbounded size these models all have the same expressive power and can be used to characterize a uniform version of VNP.     

Logic for update products and steps into the past

This paper provides a sound and complete proof system for a language L_e+Y that adds to Dynamic Epistemic Logic (DEL) a discrete previous-time operator as well as single symbol formulas that partially reveal the most recent event that occurred. The completeness theorem is by filtration followed by model unraveling and other model transformations. Decidability follows from the completeness proof. The degree to which it is important to include the additional single symbol formulas is addressed in a discussion about the difficulties of the completeness for a language L_Y that only adds the previous-time operator to DEL. Discussion is also given regarding the completeness for a language obtained by removing common knowledge operators from L_e+Y.     

A fuzzy clustering application to precise orbit determination

In recent years, fuzzy logic techniques have been successfully applied in geodesy problems, in particular to GPS. The aim of this work is to test a fuzzy-logic method with an enhanced probability function as a tool to provide a reliable criteria for weighting scheme for satellite-laser-ranging (SLR) station observations, seeking to optimize their contribution to the precise orbit determination (POD) problem. The data regarding the stations were provided by the International Laser Ranging Service (ILRS), NASA/Crustal Dynamics Data Information System (CDDIS) provided the satellite data for testing the method. The software for processing the data is GEODYN II provided by NASA/Goddard Space Flight Center (GSFC). Factors to be considered in the fuzzy-logic clustering are: the total number of LAGEOS passes during the past 12 months, the stability measure of short- and long-term biases, the percentage of LAGEOS normal points that were accepted in CSR weekly LAGEOS analysis, and the RMS uncertainty of the station coordinates. A fuzzy-logic statistical method allows classifying the stations through a clear ‘degree of belonging’ to each station group. This degree of belonging translates into a suitable weight to be assigned to each station in the global solution. The first tests carried out showed improvements in the RMS of the global POD solution as well as individual stations, to within a few millimeters. We expect further work would lead to further improvements.     

An Algebraic Approach to Knowledge Base Models Informational Equivalence

In this paper we study the notion of knowledge from the positions of universal algebra and algebraic logic. We consider first order knowledge which is based on first order logic. We define categories of knowledge and knowledge base models. These notions are defined for the fixed subject of knowledge. The key notion of informational equivalence of two knowledge base models is introduced. We use the idea of equivalence of categories in this definition. We prove that for finite models there is a clear way to determine whether the knowledge base models are informationally equivalent.     

Hybrid Answer Set Programming

This paper discusses an extension of Answer Set Programming (ASP) called Hybrid Answer Set Programming (H-ASP) which allows the user to reason about dynamical systems that exhibit both discrete and continuous aspects. The unique feature of Hybrid ASP is that it allows the use of ASP type rules as controls for when to apply algorithms to advance the system to the next position. That is, if the prerequisites of a rule are satisfied and the constraints of the rule are not violated, then the algorithm associated with the rule is invoked.     

Identifying key missing data for inference under uncertainty

In many applications of knowledge-based systems, initial facts are insufficient to lead to any conclusion, and the systems need to ask users to provide more information. A question-asking strategy decides the questions to ask and their sequence. We present a question-asking strategy for Horn clause knowledge bases under uncertainties. The strategy selects questions quickly by considering both conclusion certainties and costs of reaching conclusions. The experiments on randomly generated knowledge bases show that the proposed strategy is significantly better than the contingent strategies being used with forward-chaining or backward-chaining procedures.     

ON THE ORDER PROPERTIES OF DIGITAL CURVES IN THE PAN-EUCLIDEAN GEOMETRY

How to increase the speed in drawing and recognizing curves has always been a major concern. From the Breshenham Algorithm and DDA Algorithm in the sixties to the double-step and quadruple-step line generation iu the eighties, curves were all dragon point by point. The algorithm in this paper fully utilizes machine commands to accelerate the generation of lines and curves. We introduce and prove for the first time characterization theorems of the segment code order of digital lines and curyes. These theorems give new methods in the recognition and the measure of smoothness of lines and curves.     

Construction of universal modal worlds based on hyperset theory

Knowledge modal formulas are interpreted by a universal modal world in the hypersets universe [A]. This remedies the limitation of the interpretation of knowledge formulas by a tower of modal worlds in the well founded universe [F], where each world can interpret only a portion of knowledge modal formulas. Received: 21 August 1995