We present a bimodal logic suitable for formalizing reasoning about points and sets, and also states of the world and views about them. The most natural interpretation of the logic is in subset spaces, and we obtain complete axiomatizations for the sentences which hold in these interpretations. In addition, we axiomatize the validities of the smaller class of topological spaces in a system we call topologic. We also prove decidability for these two systems. Our results on topologic relate early work (...) of McKinsey on topological interpretations of S4 with recent work of Georgatos on topologic. Some of the results of this paper were presented at the 1992 conference on Theoretical Aspects of Reasoning about Knowledge. (shrink)

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. (shrink)

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: Allxareyand Somexarey, There are at least as manyxasy, and There are morexthany. Herexandyrange over subsets (not elements) of a giveninfiniteset. Moreover,xandymay appear complemented (i.e., as$\bar{x}$and$\bar{y}$), 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. (shrink)

In Pietroski ( 2018 ) a simple representation language called SMPL is introduced, construed as a hypothesis about core conceptual structure. The present work is a study of this system from a logical perspective. In addition to establishing a completeness result and a complexity characterization for reasoning in the system, we also pinpoint its expressive limits, in particular showing that the fourth corner in the square of opposition (“ Some_not ”) eludes expression. We then study a seemingly small extension, called (...) SMPL +, which allows for a minimal predicate-binding operator. Perhaps surprisingly, the resulting system is shown to encode precisely the concepts expressible in first-order logic. However, unlike the latter class, the class of SMPL + expressions admits a simple procedural (context-free) characterization. Our contribution brings together research strands in logic—including natural logic, modal logic, description logic, and hybrid logic—with recent advances in semantics and philosophy of language. (shrink)

This paper enlarges classical syllogistic logic with assertions having to do with comparisons between the sizes of sets. So in addition to assertions like All x are y and Some x are y, we also have There are at least as many x as y, and There are more x than y. Our work also allows all nouns to be complemented. We thus obtain sentences equivalent to No x are y and At least half of the universe are x. We (...) work on finite models exclusively. We formulate a syllogistic logic for our language. The main result is a soundness/completeness theorem. The logic has a rule of ex falso quodlibet, and reductio ad absurdum is admissible. There are efficient algorithms for proof search and model construction, and the logic has been implemented. (shrink)

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 11–complete. Two of these fragments (...) do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 01–complete. These results go via reduction to problems concerning domino systems. (shrink)

This paper obtains the weak completeness and decidability results for standard systems of modal logic using models built from formulas themselves. This line of work began with Fine (Notre Dame J. Form. Log. 16:229-237, 1975). There are two ways in which our work advances on that paper: First, the definition of our models is mainly based on the relation Kozen and Parikh used in their proof of the completeness of PDL, see (Theor. Comp. Sci. 113-118, 1981). The point is to (...) develop a general model-construction method based on this definition. We do this and thereby obtain the completeness of most of the standard modal systems, and in addition apply the method to some other systems of interest. None of the results use filtration, but in our final section we explore the connection. (shrink)

This paper adds comparative adjectives to two systems of syllogistic logic. The comparatives are interpreted by transitive and irreflexive relations on the underlying domain. The main point is to obtain sound and complete axiomatizations of the valid formulas in the logics.

This thesis is intended t0 help develop the theory 0f coalgebras by, Hrst, taking classic theorems in the theory 0f universal algebras amd dualizing them and, second, developing an interna] 10gic for categories 0f coalgebras. We begin with an introduction t0 the categorical approach t0 algebras and the dual 110tion 0f coalgebras. Following this, we discuss (c0)a,lg€bra.s for 2. (c0)monad and develop 2. theory 0f regular subcoalgebras which will be used in the interna] logic. We also prove that categories 0f (...) coalgebras are completc, under reasonably weak conditions, and simultaneously prove the wellknown dual result for categories 0f algebras. We dose the second chapter with 2. discussion 0f bisimulations in which we introduce a weaker 110tion 0f bisimulaticn than is current in the literature, but which is w€H—b€ha.v€d and reduces t0 the standard defmition under the assumption 0f choice. (shrink)

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.

Description logics and logics in the newer area of ‘natural logics’ are typically weak but interesting and tractable fragments of first-order logic. The logics involved are sometimes called ‘term logics’, where a term is something interpreted as a subset of a given model, and they usually lack individual variables. They are extensions of syllogistic logics and weakenings of first-order logic. This paper discusses description logics and natural logics and then presents logics which connect the two areas. The emphasis is on (...) completeness results for the logics at hand. So we bring to the description logic area logics that are loosely based on natural language constructions (as is typical of natural logics), and completeness results for them. In the other direction, we bring to natural logics the distributive lattice operations on concepts (nouns) that have so far been missing and that are typical of description logics. (shrink)

This paper provides a foundation for the polarity marking technique introduced by David Dowty [3] in connection with monotonicity reasoning in natural language and in linguistic analyses of negative polarity items based on categorial grammar. Dowty's work is an alternative to the better-known algorithmic approach first proposed by Johan van Benthem [11], and elaborated by Víctor Sánchez Valencia [10]. Dowty's system internalized the monotonicity/polarity markings by generating strings using a categorial grammar whose categories already contain the markings that the earlier (...) system would obtain by separate steps working on an already-derived string. Despite the linguistic advantages of the internalized system, no soundness proof has yet been given for it. This paper offers an account. The leading mathematical idea is to interpret categorial types as preorders (in order to talk about monotonicity in the first place), and then to add a primitive operation to the type hierarchy of taking the opposite of a preorder (in order to capture monotone decreasing functions). At the same time, the use of internalized categories also raises issues. Although these will not be addressed in full, the paper points out possible approaches to them. (shrink)

This paper considers the correspondence theory from modal logic and obtains correspondence results for models as opposed to frames. The key ideas are to consider infinitary modal logic, to phrase correspondence results in terms of substitution instances of a given modal formula, and to identify bisimilar model-world pairs.

We consider the use ofevolving algebra methods of specifying grammars for natural languages. We are especially interested in distributed evolving algebras. We provide the motivation for doing this, and we give a reconstruction of some classic grammar formalisms in directly dynamic terms. Finally, we consider some technical questions arising from the use of direct dynamism in grammar formalisms.

Edited in collaboration with FoLLI, the Association of Logic, Language and Information this book constitutes the refereed proceedings of the 22nd Workshop on Logic, Language, Information and Computation, WoLLIC 2015, held in the campus of Indiana University, Bloomington, IN, USA in July 2015. The 14 contributed papers, presented together with 8 invited lectures and 4 tutorials, were carefully reviewed and selected from 44 submissions. The focus of the workshop was on interdisciplinary research involving formal logic, computing and programming theory, and (...) natural language and reasoning. (shrink)

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR 0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.

We present a rendering of some common grammatical formalisms in terms of evolving algebras. Though our main concern in this paper is on constraint-based formalisms, we also discuss the more basic case of context-free grammars. Our aim throughout is to highlight the use of evolving algebras as a specification tool to obtain grammar formalisms.

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]. (shrink)

This book discusses major milestones in Rohit Parikh’s scholarly work. Highlighting the transition in Parikh’s interest from formal languages to natural languages, and how he approached Wittgenstein’s philosophy of language, it traces the academic trajectory of a brilliant scholar whose work opened up various new avenues in research. This volume is part of Springer’s book series Outstanding Contributions to Logic, and honours Rohit Parikh and his works in many ways. Parikh is a leader in the realm of ideas, offering concepts (...) and definitions that enrich the field and lead to new research directions. Parikh has contributed to a variety of areas in logic, computer science and game theory. In mathematical logic his contributions have been in recursive function theory, proof theory and non-standard analysis; in computer science, in the areas of modal, temporal and dynamic logics of programs and semantics of programs, as well as logics of knowledge; in artificial intelligence in the area of belief revision; and in game theory in the formal analysis of social procedures, with a strong undercurrent of philosophy running through all his work. This is not a collection of articles limited to one theme, or even directly connected to specific works by Parikh, but instead all papers are inspired and influenced by Parikh in some way, adding structures to and enriching “Parikh-land”. (shrink)