Many natural language processing (NLP) applications require the computation of similarities between pairs of syntactic or semantic trees. Many researchers have used tree edit distance for this task, but this technique suffers from the drawback that it deals with single node operations only. We have extended the standard tree edit distance algorithm to deal with subtree transformation operations as well as single nodes. The extended algorithm with subtree operations, TED+ST, is more effective and flexible than the standard algorithm, especially for applications that pay attention to relations among nodes (e.g. in linguistic trees, deleting a modifier subtree should be cheaper than the sum of deleting its components individually). We describe the use of TED+ST for checking entailment between two Arabic text snippets. The preliminary results of using TED+ST were encouraging when compared with two string-based approaches and with the standard algorithm.

Work on speech acts has generally involved the introduction of sets of different actions such as informing, reminding, bluffing and lying. These actions have different preconditions and effects, and hence can be used to achieve a wide variety of different real-world goals. The problem is that they tend to have indistinguishable surface forms. As such, it is extremely difficult for the hearer to decide which action she thinks has been performed, and it is therefore also extremely difficult for the speaker to be confident about how the hearer will respond. We will show how to achieve complex goals on the basis of a very simple set of linguistic actions. These actions have clearly marked surface forms, and hence can easily be distinguishable by a hearer. In order to do this, we have developed an epistemic planner with a number of interesting features, and with a number of optimisations that relate directly to aspects of the task at hand.

Many natural languages use prepositions to mark relations between entities of various kinds-between physical entities and their spatial locations, between temporal entities and their temporal locations, between abstract entities of various kinds (e.g. between ideas and their 'mental locations'). I show that the consequences of using prepositions to relate temporal entities emerge naturally from the basic interpretations of the prepositions themselves together with a very weak logic of events, where I take it that prepositions denote abstract relations whose significance only emerges when properties of the related items are taken into consideration.

Most parsing algorithms require phrases that are to be combined to be either contiguous or marked as being ‘extraposed’. The assumption that phrases which are to be combined will be adjacent to one another supports rapid indexing mechanisms: the fact that in most languages items can turn up in unexpected locations cancels out much of the ensuing efficiency. The current paper shows how ‘out of position’ items can be incorporated directly. This leads to efficient parsing even when items turn up having been right-shifted, a state of affairs which makes Johnson and Kay's (1994) notion of ‘sponsorship’ of empty nodes inapplicable.

It is often convenient to be able to save and subsequently restore the state of a computation. It is also, in general, rather expensive. We present a technique whereby states may be saved and restored extremely fast, and yet the information stored in a given state may be accessed and updated reasonably quickly. This technique depends on an indexing scheme which can be used to see whether the last value assigned to a variable is still valid, or whether it must be retrieved from some previous context.

Abstract This paper describes an interactive programming environment within which proposed changes to a program are monitored to ensure that they do not introduce various common types of logical inconsistency. The environment, which is provided by a network of concurrent ‘experts’ dealing with various aspects of the program being developed, is designed to be convenient to work in and to impose few constraints on the programmer.