Search

We build and study dynamic versions of epistemic logic. We study languages parameterized by an action signature that allows one to express epistemic actions such as (truthful) public announcements, completely private announcements to groups of agents, and more. The language L (Σ) is modeled on dynamic logic. Its sentence-building operations include modalities for the execution of programs, and for knowledge and common knowledge. Its program-building operations include action execution, composition, repetition, and choice. We consider two fragments of L (Σ) . In L 1 (Σ) , we drop action repetition; in L 0 (Σ) , we also drop common knowledge. We present the syntax and semantics of these languages and sound proof systems for the validities in them. We prove the strong completeness of a logical system for L 0 (Σ) and the weak completeness of one for L 1 (Σ) . We show the finite model property and, hence, decidability of L 1 (Σ) . We translate L 1 (Σ) into PDL, obtaining a second proof of decidability. We prove results on expressive power, comparing L 1 (Σ) with modal logic together with transitive closure operators. We prove that a logical language with operators for private announcements is more expressive than one for public announcements. [ABSTRACT FROM AUTHOR]

Against the backdrop of the ever-improving Natural Language Inference (NLI) models, recent efforts have focused on the suitability of the current NLI datasets and on the feasibility of the NLI task as it is currently approached. Many of the recent studies have exposed the inherent human disagreements of the inference task and have proposed a shift from categorical labels to human subjective probability assessments, capturing human uncertainty. In this work, we show how neither the current task formulation nor the proposed uncertainty gradient are entirely suitable for solving the NLI challenges. Instead, we propose an ordered sense space annotation, which distinguishes between logical and common-sense inference. One end of the space captures non-sensical inferences, while the other end represents strictly logical scenarios. In the middle of the space, we find a continuum of common-sense, namely, the subjective and graded opinion of a "person on the street." To arrive at the proposed annotation scheme, we perform a careful investigation of the SICK corpus and we create a taxonomy of annotation issues and guidelines. We re-annotate the corpus with the proposed annotation scheme, utilizing four symbolic inference systems, and then perform a thorough evaluation of the scheme by fine-tuning and testing commonly used pre-trained language models on the re-annotated SICK within various settings. We also pioneer a crowd annotation of a small portion of the MultiNLI corpus, showcasing that it is possible to adapt our scheme for annotation by non-experts on another NLI corpus. Our work shows the efficiency and benefits of the proposed mechanism and opens the way for a careful NLI task refinement. [ABSTRACT FROM AUTHOR]

This paper explores relational syllogistic logics, a family of logical systems related to reasoning about relations in extensions of the classical syllogistic. These are all decidable logical systems. We prove completeness theorems and complexity results for a natural subfamily of relational syllogistic logics, parametrized by constructors for terms and for sentences. [ABSTRACT FROM AUTHOR]

This article enlarges classical syllogistic logic with assertions having to do with comparisons between the sizes of sets. So it concerns a logical system whose sentences are of the following forms: All x are y and Some x are y , There are at least as many x as y , and There are more x than y. Here x and y range over subsets (not elements) of a given infinite set. Moreover, x and y may appear complemented (i.e., as x and ӯ), with the natural meaning. We formulate a logic for our language that is based on the classical syllogistic. The main result is a soundness/completeness theorem. There are efficient algorithms for proof search and model construction. [ABSTRACT FROM AUTHOR]

We add Most X are Y to the syllogistic logic of All X are Y and Some X are Y. We prove soundness, completeness, and decidability in polynomial time. Our logic has infinitely many rules, and we prove that this is unavoidable. [ABSTRACT FROM AUTHOR]

A majority digraph is a finite simple digraph G =(V,→) such that there exist finite sets Av for the vertices ν ∈ V with the following property: u → v if and only if "more than half of the Au are Av". That is, u → v if and only if |Au ∩ Av| > 1/2 |Au|. We characterize the majority digraphs as the digraphs with the property that every directed cycle has a reversal. If we change 1/2 to any real number α ∈ (0, 1), we obtain the same class of digraphs. We apply the characterization result to obtain a result on the logic of assertions "most X are Y " and the standard connectives of propositional logic. [ABSTRACT FROM AUTHOR]

Terminal coalgebras for a functor serve as semantic domains for state-based systems of various types. For example, behaviors of CCS processes, streams, infinite trees, formal languages and non-well-founded sets form terminal coalgebras. We present a uniform account of the semantics of recursive definitions in terminal coalgebras by combining two ideas: (1) abstract GSOS rules ℓ specify additional algebraic operations on a terminal coalgebra; (2) terminal coalgebras are also initial completely iterative algebras (cias). We also show that an abstract GSOS rule leads to new extended cia structures on the terminal coalgebra. Then we formalize recursive function definitions involving given operations specified by ℓ as recursive program schemes for ℓ, and we prove that unique solutions exist in the extended cias. From our results it follows that the solutions of recursive (function) definitions in terminal coalgebras may be used in subsequent recursive definitions which still have unique solutions. We call this principle modularity. We illustrate our results by the five concrete terminal coalgebras mentioned above, e. g., a finite stream circuit defines a unique stream function. [ABSTRACT FROM AUTHOR]

For endofunctors of varieties preserving intersections, a new description of the final coalgebra and the initial algebra is presented: the former consists of all well-pointed coalgebras. These are the pointed coalgebras having no proper subobject and no proper quotient. The initial algebra consists of all well-pointed coalgebras that are well-founded in the sense of Osius [22] and Taylor [29]. And initial algebras are precisely the final well-founded coalgebras. Finally, the initial iterative algebra consists of all finite wellpointed coalgebras. Numerous examples are discussed e.g. automata, graphs, and labeled transition systems. [ABSTRACT FROM AUTHOR]

This article has two purposes. The first is to present a final coalgebra construction for finitary endofunctors on Set that uses a certain subset L* of the limit L of the first ω terms in the final sequence. L* is the set of points in L which arise from all coalgebras using their canonical morphisms into L, and it was used earlier for different purposes in Kurz and Pattinson (2005, Mathematical Structures in Computer Science, 15, 543–473). Viglizzo (2005, PhD Dessertation, Indiana University) showed that the same set L* carried a final coalgebra structure for functors in a certain inductively defined family. Our first goal is to generalize this to all finitary endofunctors; the result is implicit in Worrell (2005, Theoritical Computer Science, 338, 184–199). The second goal is to use the final coalgebra construction to propose coalgebraic logics similar to those in Lawrence S. Moss (1999, Annals of Pure and Applied Logic, 96, 277–317) but for all finitary endofunctors F on Set. This time one can dispense with all conditions on F, construct a logical language ℒF directly from it, and prove that two points in a coalgebra satisfy the same sentences of ℒF iff they are identified by the final coalgebra morphism. The language ℒF is very spare, having no boolean connectives. This work on ℒF is thus a re-working of coalgebraic logic for finitary functors on sets. [ABSTRACT FROM PUBLISHER]

This article provides sound and complete logical systems for several fragments of English which go beyond syllogistic logic in that they use verbs as well as other limited syntactic material: universally and existentially quantified noun phrases, building on the work of Nishihara, Morita and Iwata (1990, Systems and Computers in Japan, 21, 96–111); complemented noun phrases, following our Moss (2007, Syllogistic Logic with Complements); and noun phrases which might contain relative clauses, recursively, based on McAllester and Givan (1992, Artifical Intelligence, 56, 1–20). The logics are all syllogistic in the sense that they do not make use of individual variables. Variables in our systems range over nouns, and in the last system, over verbs as well. [ABSTRACT FROM PUBLISHER]

The Aristotelian syllogistic cannot account for the validity of certain inferences involving relational facts. In this paper, we investigate the prospects for providing a relational syllogistic. We identify several fragments based on (a) whether negation is permitted on all nouns, including those in the subject of a sentence; and (b) whether the subject noun phrase may contain a relative clause. The logics we present are extensions of the classical syllogistic, and we pay special attention to the question of whether reductio ad absurdum is needed. Thus our main goal is to derive results on the existence (or nonexistence) of syllogistic proof systems for relational fragments. We also determine the computational complexity of all our fragments. [ABSTRACT FROM AUTHOR]

We consider foundational questions related to the definition of functions by corecursion. This method is especially suited to functions into the greatest fixed point of some monotone operator, and it is most applicable in the context of non-wellfounded sets. We review the work on the Special Final Coalgebra Theorem of Aczel [1] and the Corecursion Theorem of Barwise and Moss [4]. We offer a condition weaker than Aczel's condition of uniformity on maps, and then we prove a result relating the operators satisfying the new condition to the smooth operators of [4]. [ABSTRACT FROM PUBLISHER]

This article is intended to provide evidence that the phenomenon of Platonic deception has played a curious and distinctive role in shaping thought about the administration of social order. According to the reading of Plato's Republic, deception is what is needed if the personal interests and motivations of citizens are to be aligned in ways that allow a region to escape ordinary subsistence and enjoy luxurious consumption opportunities instead. According to the Platonic conception of the importance of deception in promoting social organization, the answer to both these questions is a resounding no. Plato did not offer the old adage about ignorance being bliss because, as have been seen, those few in authority are not ignorant at all about what is going on. Rather, the ignorance is confined to the rank-and-file citizenry. The less individuals know about the debauched sources of their prosperity, the more likely that prosperity will endure. Debunkers of the fully-informed-citizen myth do put their ideas in writing and publish their arguments.