This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML (eXtensible Markup Language) documents, we revisit the language. This renewed interest (...) comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical (second-order) problems, like the boolean circuit and the frontier problem. (shrink)

It is a widely held view in philosophy that propositions perform a plethora of different theoretical roles. Amongst other things, they are believed to be the semantic values of sentences in contexts, the objects of attitudes, the contents of illocutionary acts, and the referents of that-clauses. This assumption is often combined with the claim that propositions have their truth-values eternally. In this paper I aim to show that these two assumptions are incompatible: propositions cannot both fulfill the mentioned roles and (...) be eternally true or false. Following Kaplan and Lewis’s Operator Argument, I argue that compositional semantic values of sentences in contexts do not correspond to eternal propositions. Thus, either we regard the non-eternal entities that in fact realize the semantic role of propositions as also fulfilling the remaining propositional roles, or we abandon the assumption that there is a unique realizer of all the roles. The Operator Argument has recently come under attack, mainly for its tense-logical assumptions. However, rejecting these assumptions is not a sufficient defense of the compatibility of the two claims, since the extensional alternative to the tense-logical framework does not allow us to universally retain eternal propositions as compositional semantic values of sentences either. (shrink)

This paper explains how to obtain quantification over times in a tense logic in which all temporal distinctions are ultimately spelled out in terms of the two simple tense operators “it was the case that” and “it will be the case that.” The account of times defended here is similar to what is known as “linguistic ersatzism” about possible worlds, but there are noteworthy differences between these two cases. For example, while linguistic ersatzism would support actualism, the view of times (...) defended here does not support presentism. (shrink)

According to Hans Kamp and Frank Vlach, the two-dimensional tense operators “now” and “then” are ineliminable in quantified tense logic. This is often adduced as an argument against tense logic, and in favor of an extensional account that makes use of explicit quantification over times. The aim of this paper is to defend tense logic against this attack. It shows that “now” and “then” are eliminable in quantified tense logic, provided we endow it with enough quantificational structure. The operators might (...) not be redundant in some other systems of tense logic, but this merely indicates a lack of quantificational resources and does not show any deep-seated inability of tense logic to express claims about time. The paper closes with a brief discussion of the modal analogue of this issue, which concerns the role of the actuality operator in quantified modal logic. (shrink)

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations (...) from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction.This paper deals mainly with technical aspects of our dynamic modal logic. It gives an exact description of the expressive power of this language; it also contains results on decidability for the language with arbitrary structures and for the special case with a restricted class of admissible structures. In addition, a complete axiomatization is given. The paper concludes with a remark about the modal algebras appropriate for our dynamic modal logic, and some questions for further work. (shrink)

Logic has pride of place in mathematics and its 20th century offshoot, computer science. Modern symbolic logic was developed, in part, as a way to provide a formal framework for mathematics: Frege, Peano, Whitehead and Russell, as well as Hilbert developed systems of logic to formalize mathematics. These systems were meant to serve either as themselves foundational, or at least as formal analogs of mathematical reasoning amenable to mathematical study, e.g., in Hilbert’s consistency program. Similar efforts continue, but have been (...) expanded by the development of sophisticated methods to study the properties of such systems using proof and model theory. In parallel with this evolution of logical formalisms as tools for articulating mathematical theories (broadly speaking), much progress has been made in the quest for a mechanization of logical inference and the investigation of its theoretical limits, culminating recently in the development of new foundational frameworks for mathematics with sophisticated computer-assisted proof systems. In addition, logical formalisms developed by logicians in mathematical and philosophical contexts have proved immensely useful in describing theories and systems of interest to computer scientists, and to some degree, vice versa. Three examples of the influence of logic in computer science are automated reasoning, computer verification, and type systems for programming languages. (shrink)

Weakly Aggregative Modal Logic ) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. \ has interesting applications on epistemic logic, deontic logic, and the logic of belief. In this paper, we study some basic model theoretical aspects of \. Specifically, we first give a van Benthem–Rosen characterization theorem of \ based on an intuitive notion of bisimulation. Then, in contrast to many well known normal or non-normal modal logics, we show that (...) each basic \ system \ lacks Craig interpolation. Finally, by model theoretical techniques, we show that an extension of \ does have Craig interpolation, as an example of amending the interpolation problem of \. (shrink)

ABSTRACT This paper defends a controversial view about personal identity. It argues that it is possible to endorse both Phenomenalism and Materialism about persons. Phenomenalism is the view that personal identity is grounded in phenomenal consciousness. Materialism is the view that we are material objects. Many believe that the two views are incompatible. In this paper, I show that it is possible to accept both. I consider two objections against their combination—the argument from disembodiment and an important objection by Tim (...) Bayne. My responses are based on Kripke’s analysis of necessary a posteriori and contingent a priori statements. I make the case that both objections rest on different kinds of modal illusions. This strategy can be applied to other arguments, and the paper is intended to advocate a general approach to personal identity. (shrink)

This paper considers proof-theoretic semantics for necessity within Dummett's and Prawitz's framework. Inspired by a system of Pfenning's and Davies's, the language of intuitionist logic is extended by a higher order operator which captures a notion of validity. A notion of relative necessary is defined in terms of it, which expresses a necessary connection between the assumptions and the conclusion of a deduction.

Weakly Aggregative Modal Logic (WAML) is a collection of disguised polyadic modal logics with n-ary modalities whose arguments are all the same. WAML has some interesting applications on epistemic logic and logic of games, so we study some basic model theoretical aspects of WAML in this paper. Specifically, we give a van Benthem-Rosen characterization theorem of WAML based on an intuitive notion of bisimulation and show that each basic WAML system Kn lacks Craig Interpolation.

Relativized Metaphysical Modality (RMM: Murray and Wilson, 'Relativized metaphysical modality', Oxford Studies in Metaphysics, 2012; Murray, Perspectives on Modal Metaphysics, 2017) exploits 'two-dimensionalist' resources to metaphysical, rather than epistemological, ends: the second dimension offers perspective-dependence without contingency, diverting attacks on 'Classical' analyses of modals (in effect, analyses validating S5 and the Barcan Formulae). Here, we extend the RMM program in two directions. First, we harvest resources for RMM from Lewis's 1980 'Context--Index' (CI) framework: (a) the ban in CI on binding (...) into context-arguments (akin to Kaplan's 'monstrosity' ban) projects a bright line between perspective-dependence and contingency; and (b) CI-postulated connections among meaning, content, truth, argument-structure, context, and modality collectively generate a 'Generalized Humphrey Problem' for any non-Classical analysis (examples covered include appeals to accessibility, contingent domains, and counterpart relations). Second, we sharpen the tools of RMM-based metaphysical analysis, and extend their domain of coverage across familiar anomalies for Classical modals: we revisit earlier RMM-based bulwarks for S5 (against 'Chisholm's Paradox' for moderate flexibility of essence, and nomological necessitarianism); and we now similarly shore up the Barcan Formulae (against the apparent contingency of existence and nonexistence). (shrink)

We introduce a new way of defining metric temporal logic on a real-numbers flow of time. The idea is based on having semantics which allow us to refer to a single universal clock of arbitrary precision in order to impose metric constraints. This gives us a new metric temporal logic which is very expressive, is natural to use, can be applied in very general situations, affords a wide range of useful abbreviations and operators, has a PSPACE decision procedure, and has (...) the promise of being amenable to standard reasoning techniques. Thus it has many advantages over the existing metric temporal logics. We provide a decision procedure via conversion to a non-metric temporal logic, hence doing metric reasoning with no clocks. (shrink)

This paper contains a survey of the main definitions and results obtained to date related to Temporal Equilibrium Logic, a nonmonotonic hybrid approach that combines Equilibrium Logic (the best-known logical characterisation for the stable models semantics of logic programs) with Linear-Time Temporal Logic.

A-theorists think there is a fundamental difference between the present and other times. This concern shows up in what kinds of properties they take to be instantiated, what objects they think exist and how they formalize their views. Nearly every contemporary A-theorist assumes that her metaphysics requires a tense logic – a logic with operators like and. In this paper, I show that there is at least one viable A-theory that does not require a logic with tense operators. And I (...) will argue that three common indispensability arguments for tense operators are unsound. (shrink)

The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the size of the (...) input sentence and n the size of the input word. We establish a number of similar lower bounds for the model-checking problem for first-order logic, for example, on the class of all trees. (shrink)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 BASIC MODAL LOGIC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.

This paper expands on the theory of event structures put forward in previous work by further investigating the subtle connections between time and events. Specifically, in the first part we generalize the notion of an event structure to that of a refinement structure, where various degrees of temporal granularity are accommodated. In the second part we investigate how these structures can account for the context-dependence of temporal structures in natural language semantics.

While monadic second-order logic (MSO) has played a prominent role in model theoretic syntax, modal logics have been used in this context since its inception. When comparing propositional dynamic logic (PDL) to MSO over trees, Kracht (1997) noted that there are tree languages that can be defined in MSO that can only be defined in PDL by adding new features whose distribution is predictable. He named such features “inessential features”. We show that Kracht’s observation can be extended to other modal (...) logics of trees in two ways. First, we demonstrate that for each stronger logic, there exists a tree language that can only be defined in a weaker logic with inessential features. Second, we show that any tree language that can be defined in a stronger logic, but not in some weaker logic, can be defined with inessential features. Additionally, we consider Kracht’s definition of inessential features more closely. It turns out that there are features whose distribution can be predicted, but who fail to be inessential in Kracht’s sense. We will look at ways to modify his definition. (shrink)

This essay will examine some rather serious trouble confronting claims that mathematicalia might be social constructs. Because of the clarity with which he makes the case and the philosophical rigor he applies to his analysis, our exemplar of a social constructivist in this sense is Julian Cole, especially the work in his 2009 and 2013 papers on the topic. In a 2010 paper, Jill Dieterle criticized the view in Cole’s 2009 paper for being unable to account for the atemporality of (...) mathematical existents. Cole’s 2013 paper addresses this objection, providing a modification of his 2009 paper allowing for atemporal mathematicalia. An unusual consequence of Cole’s account is that at least some existential claims about mathematicalia used to be false but now have always been true. By examining the semantics of such claims, we demonstrate that social constructivism is in fact, despite Cole’s attempts to rectify matters, incompatible with atemporal mathematicalia. In the course of examining these semantic details, however, an alternative hybrid view of fictionalism and social constructivism emerges. Those tempted by social constructivism, while perhaps disappointed by the negative results of the paper, may be encouraged by how much of their view can be recovered in this alternative account. (shrink)

In many logics dealing with information one needs to make statements not only about cognitive states, but also about transitions between them. In this paper we analyze a dynamic modal logic that has been designed with this purpose in mind. On top of an abstract information ordering on states it has instructions to move forward or backward along this ordering, to states where a certain assertion holds or fails, while it also allows combinations of such instructions by means of operations (...) from relation algebra. In addition, the logic has devices for expressing whether in a given state a certain instruction can be carried out, and whether that state can be arrived at by carrying out a certain instruction. This paper deals mainly with technical aspects of our dynamic modal logic. It gives an exact description of the expressive power of this language; it also contains results on decidability for the language with 'arbitrary' structures and for the special case with a restricted class of admissible structures. In addition, a complete axiomatization is given. The paper concludes with a remark about the modal algebras appropriate for our dynamic modal logic, and some questions for further work. The paper only contains some sketchy examples showing how the logic can be used to capture situations of dynamic interest, far more detailed applications are given in a companion to this paper (De Rijke [33]). (shrink)

Trees with indistinguishability relations provide a semantics for a temporal language “composed by” the Peircean tense operators and the Ockhamist modal operator. In this paper, a finite axiomatization with a non standard rule for this language interpreted over bundled trees with indistinguishability relations is given. This axiomatization is proved to be sound and strongly complete.

ABSTRACT In this paper we present a new semantic approach for propositional linear temporal logic with discrete time, strongly based in the well-order of IN (the set of natural numbers). We consider temporal connectives which express precedence, posteriority and simultaneity, and they provide a family of expressively complete temporal logics. The selection of the new semantics and connectives used in this work was principally to obtain a suitable executable temporal logic, which can be used for the specification and control of (...) process behaviour in discrete time in a similar way to thai presented by D. Gabbay in [GAB 89], Our new approach has two advantages: firstly, the connectives are defined intuitively so that they have interpretations which relate to properties of interest in real systems; secondly, it provides a new semantics that facilitates simpler proofs of many valid formulas and metatheorems. To confirm this second advantage, we use our semantics to give a formal proof of the Separation Theorem for one of these logics (specifically LN3). The great interest of this Separation Theorem for the executable temporal logic is emphasised by D. Gabbay in [GAB 89], [GAB 88]. (shrink)