We construct logical languages which allow one to represent a variety of possible types of changes affecting the information states of agents in a multi-agent setting. We formalize these changes by defining a notion of epistemic program. The languages are two-sorted sets that contain not only sentences but also actions or programs. This is as in dynamic logic, and indeed our languages are not significantly more complicated than dynamic logics. But the semantics is more complicated. In general, the semantics of (...) an epistemic program is what we call aprogram model. This is a Kripke model of ‘actions’,representing the agents' uncertainty about the current action in a similar way that Kripke models of ‘states’ are commonly used in epistemic logic to represent the agents' uncertainty about the current state of the system. Program models induce changes affecting agents' information, which we represent as changes of the state model, called epistemic updates. Formally, an update consists of two operations: the first is called the update map, and it takes every state model to another state model, called the updated model; the second gives, for each input state model, a transition relation between the states of that model and the states of the updated model. Each variety of epistemic actions, such as public announcements or completely private announcements to groups, gives what we call an action signature, and then each family of action signatures gives a logical language. The construction of these languages is the main topic of this paper. We also mention the systems that capture the valid sentences of our logics. But we defer to a separate paper the completeness proof. (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)
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)
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 of a given infinite set. Moreover, x and y may appear complemented, 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 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 provides a foundation for the polarity marking technique introduced by David Dowty  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 , and elaborated by Víctor Sánchez Valencia . 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.
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 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.
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 . 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.