This paper presents a formalization of refraining from actions and a deontic logic based on a process logic. The notion of refraining is needed to handle obligated actions. To refrain to do an action is to do something else. The process logic used is a mix of dynamic logic and temporal logic: actions in it are interpreted as sets of paths and temporal formulas describe the process of performing actions. The deontic logic has a temporal propositional constant saying that a bad thing will be done in the next moment. Normative properties of actions can be defined according to what happens in the process of performing actions.

Dynamic Epistemic Logic (DEL) can model complex information scenarios in a way that appeals to logicians. However, existing DEL implementations are ad-hoc, so we do not know how the framework really performs. For this purpose, we want to hook up with the best available model checking and SAT techniques in computational logic. We do this by first providing a bridge: a new faithful representation of DEL models as so-called knowledge structures that allow for symbolic model checking. For more complex epistemic change we introduce knowledge transformers analogous to action models. Next, we show that we can now solve well-known benchmark problems in epistemic scenarios much faster than with existing methods for DEL. We also compare our approach to model checking for temporal logics. Finally, we show that our method is not just a matter of implementation, but that it raises significant issues about logical representation and update.

We propose a framework for message passing that combines the best properties of dynamic epistemic semantics and history-based approaches. We assume that all communication is truthful and reliable. Our framework consists of Kripke models with records of sent messages in their valuations. We introduce an update operation for message sending. With this update we can study the exact epistemic consequences of sending a message. We define a class of models that is generated from initial Kripke models by means of message updates, and we axiomatize a logic for this class of models. Next, we add an update modality and sketch a procedure for defining it by means of equivalence axioms.

Epistemic protocols are communication protocols aiming at transfer of knowledge in a controlled way. Typically, the preconditions or goals for protocol actions depend on the knowledge of agents, often in nested form. Informal epistemic protocol descriptions for muddy children, coordinated attack, dining cryptographers, Russian cards, secret key exchange are well known. The contribution of this paper is a formal study of a natural requirement on epistemic protocols, that the contents of the protocol can be assumed to be common knowledge. By formalizing this requirement we can prove that there can be no unbiased deterministic protocol for the Russian cards problem. For purposes of our formal analysis we introduce an epistemic protocol language, and we show that its model checking problem is decidable.

This article defines the grammar class of sequentially indexed grammars (SIGs) that results of a change in the index stack handling mechanism of indexed grammars (Aho, 1968, Journal of the ACM, 15, 647–671; 1969, Journal of the ACM, 16, 383–406). SIGs are different from linear indexed grammars (Gazdar, 1988, Natural Language, Parsing and Linguistic, Theories, pp. 69–94) (the rule format is simpler) and they generate a strictly larger language class. We give a polynomial algorithm for parsing with SIGs that is a rather straightforward extension of the Earley algorithm for parsing with context-free grammars. SIGs are attractive because of the simple rule format, the natural correspondence between indices and traces, and the perspicuity of the parsing scheme.

Functions of type 〈n〉 are characteristic functions on n-ary relations. Keenan established their importance for natural language semantics, by showing that natural language has many examples of irreducible type 〈n〉 functions, i.e. functions of type 〈n〉 that cannot be represented as compositions of unary functions. Keenan proposed some tests for reducibility, and Dekker improved on these by proposing an invariance condition that characterizes the functions with a reducible counterpart with the same behaviour on product relations. The present paper generalizes the notion of reducibility (a quantifier is reducible if it can be represented as a composition of quantifiers of lesser, but not necessarily unary, types), proposes a direct criterion for reducibility, and establishes a diamond theorem and a normal form theorem for reduction. These results are then used to show that every positive 〈n〉 function has a unique representation as a composition of positive irreducible functions, and to give an algorithm for finding this representation. With these formal tools it can be established that natural language has examples of n ary quantificational expressions that cannot be reduced to any composition of quantifiers of lesser degree.

Abstract Presuppositions of utterances are the pieces of information you convey with an utterance no matter whether your utterance is true or not. We first study presupposition in a very simple framework of updating propositional information, with examples of how presuppositions of complex propositional updates can be calculated. Next we move on to presuppositions and quantification, in the context of a dynamic version of predicate logic, suitably modified to allow for presupposition failure. In both the propositional and the quantificational case, presupposition failure can be viewed as error abortion of procedures. Thus, a dynamic assertion logic which describes the preconditions for error abortion is the suitable tool for analysing presupposition.

Transition systems can be viewed either as process diagrams or as Kripke structures. The first perspective is that of process theory, the second that of modal logic. This paper shows how various formalisms of modal logic can be brought to bear on processes. Notions of bisimulation can not only be motivated by operations on transition systems but can also be suggested by investigations of modal formalisms. To show that the equational view of processes from process algebra is closely related to modal logic, we consider various ways of looking at the relation between the calculus of basic process algebra and propositional dynamic logic. More concretely, the paper contains preservation results for various bisimulation notions, a result on the expressive power of propositional dynamic logic, and a definition of bisimulation which is the proper notion of invariance for concurrent propositional dynamic logic.

This paper describes a 'Logical Form' target language for representing the literal meaning of English sentences, and an intermediate level of representation ('Quasi Logical Form') which engenders a natural separation between the compositional semantics and the processes of scoping and reference resolution. The approach has been implemented in the SRI Core Language Engine which handles the English constructions discussed in the paper.