The probability that intervals are related by a particular Allen relation is calculated relative to sample spaces\nΩn given by the number n of, in one case, points, and, in another, interval names. In both cases, worlds in\nthe sample space are assumed equiprobable, and Allen relations are classified as short, medium and long,\naccording to the number of shared borders.

Abstract Relations computed by finite-state transducers are applied to interpret temporal propositions in terms of strings representing finite contexts or situations. Carnap–Montague intensions mapping indices to extensions are reformulated as relations between strings that can serve as indices and extensions alike. Strings are related according to information content, temporal span and granularity, the bounds on which reflect the partiality of natural language statements. That partiality shapes not only strings-as-extensions (indicating what statements are about) but also strings-as-indices (underlying truth conditions).

Events in natural language semantics are characterized in terms of regular languages, each string in which can be regarded as a temporal sequence of observations. The usual regular constructs (concatenation, etc.) are supplemented with superposition, inducing a useful notion of entailment, distinct from that given by models of predicate logic.

Events employed in natural language semantics are characterized in terms of regular languages, each string in which can be regarded as a motion picture. The relevant finite automata then amount to movie cameras/projectors, or more formally, to finite Kripke structures with partial valuations. The usual regular constructs (concatenation, choice, etc) are supplemented with superposition of strings/automata/languages, realized model-theoretically as conjunction.

. Notions of context for natural language interpretation are factored in terms of three processes: translation, entailment and attunement. The processes are linked by accessibility relations of the kind studied in many-dimensional modal logic, modulo complications from constraints between translation and entailment (violations in which may trigger reattunement) and from refinement and underspecification. Keywords. Natural language semantics, knowledge representation 1 Introduction It is familiar practice in semantics to encode context as a sequence, selected components of which can be varied while others are held constant. The indexical now was, for instance, brought into temporal logic in Kamp [7] via an early form of multi-dimensional modal logic (Marx and Venema [10]). And to analyze speaker presuppositions, Stalnaker [14] injected content into context, feeding the development of "dynamic" approaches to semantics such as Discourse Representation Theory (DRT). The present wo...

Abstract Elementary (first-order) and nonelementary (set-theoretic) aspects of the largest bisimulation are considered with a view toward analyzing operational semantics from the perspective of predicate logic. The notion of a bisimulation is employed in two distinct ways: (i) as an extensional notion of equivalence on programs (or processes) generalizing input/output equivalence (at a cost exceeding over certain transition predicates computable in log space), and (ii) as a tool for analyzing the dependence of transitions on data (which can be shown to be elementary or nonelementary, depending on the formulation of the transitions).

The nature of programming languages that fail to have a relatively complete proof formalism is discussed. First, it is shown that such failures may be due to the meagerness of the programming language, rather than to the presence of complex control structures as in the cases studied so far. The failure of relative completeness is then derived for two languages with a rich control structure, using simple simulations of general recursive functions by procedure call mechanisms.

The notion of relative completeness of logics of programs was delineated almost ten years ago, in particular by Wand, Cook and Clarke. More recently, it has been felt that Cook's notion hinges on a fragile balance between the semantics of a programming language and first-order expressiveness in structures. This fragility underlies the negative results about relative completeness.