An Indexing Technique for Implementing Command Relations

AN INDEXING TECHNIQUE FOR IMPLEMENTING COMMAND RELATIONS Longin Latecki University of Hamburg Department of Computer Science Bodenstedtstr. 16, 2000 Hamburg 50 Germany TOPIC AREA: SYNTAX, SEMANTICS ABSTRACT Command relations are important tools in linguistics, especially in anaphora theory. In this paper I present an indexing technique which allows us to implement a simple and efficient check for most cases of command relations which have been presented in linguistic literature. I also show a wide perspective of applications for the indexing technique in the imple- mentation of other linguistic phenomena in syntax as well as in semantics. 0. INTRODUCTION Barker and Pullum (1990) have given a general definition of command relations. Their definition covers most cases of command relations that have been presented in linguistic literature. I will present here an indexing technique for syntax trees which allows us to implement a check for all command relations which fulfill the definition from Barker/Pullum (1990). The indexing technique can be implemented in a simple and efficient way without any special requierments for the formalism used. Hence, the indexing technique has a wide spectrum of applications for testing command relations in syntactic analysis. Futhermore, this method can also be used for command tests in semantics, i.e. to test for any two semantic representations whether the corresponding nodes of the syntax tree are in a command relation. The usefulness and necessity of a command test in semantics have been demonstrated in Latecki/Pinkal (1990). The general idea of the indexing technique is the following: while a syntax tree is being built, special indices are assigned to the nodes of this tree. Afterwards we can check whether a command relation between two nodes of this tree holds by merely examining simple set-theoretical relations of corresponding index sets. 1. A GENERAL DEFINITION FOR COMMAND RELATIONS The general command definition from Barker/Pullum (1990) can be informally stated in the following way: 1.1 DEFINITION (all). a P-commands 13 iff every node with a property P that properly dominates a also dominates ~. In this chapter I will show that this definition is equivalent to the following definition (minimum). 1.2 DEFINITION (minimum). a P-com- mands ~ iff the first node with a property P that properly dominates ¢x also dominates 13. In this definition the first node that dominates a means the node most immediately dominating a, as it isusually used in linguistics. Below I will specify both of these definitions formally. The main difference between these two definitions is that in the first we must check every node with a property P that properly dominates a, while in the second it is enough to check only one node, just the first node with the property P that properly diominates a. It can be easily seen that the command tests based on definition 1.2 are an important improvement in efficiency for computational applications. 4" -51 - Both versions (all) and (minimum) are used as command definitions in linguistic literature, so their equivalence also has linguistic consequences. For example, definition 1.3 …

Content truncated to 500 words