Towards a Semantics for Lexical Rules as used in HPSG

Walt Detmar Meurers Sonderforschungsbereich 340 B4/B8, University of Tübingen Kleine Wilhelmstr. 113, 72074 Tübingen, Germany E-mail: dm@sfs.nphil.uni-tuebingen.de

Revised version of the paper presented at the Conference on Formal Grammar, 12-13 August 1995, Barcelona, Spain.

Abstract

We show how a mechanism that captures the functionality of lexical rules can be integrated into the logical setup for hpsg provided by King (1989, 1994) without having to enlarge the logic with a metalevel or extra notions such as defaults. A notation for lexical rules is introduced and a rewrite system is defined to map the lexical rules as specified by the linguist into ordinary constraints in the King logic. We therefore show how a denotational semantics for lexical rules as used in hpsg linguistics can be provided.

Keywords: lexical rules, hpsg, logical issues of the hpsg architecture.

1 Introduction

Lexical rules have been used by linguists to express generalizations over the lexicon for over 25 years. In the paradigm of hpsg they have become one of the key mechanisms used in current analysis, be it for cross-serial dependencies and preposition stranding in Dutch, clitic climbing in French and Italian, verb-second, finitivization and partial constituent fronting in German, or passive formation and traceless extraction in general.

Looking at lexical rules from a logical perspective yields a less favorable picture. A formal foundation for hpsg theories has been provided and some studies of various formal and computational aspects exist, but so far no lexical rule mechanism capturing the semantics intended in hpsg linguistics has been formalized.

This paper is intended to help clarify how a lexical rule mechanism could be formalized. More specifically, we show how a mechanism that captures the functionality of hpsg lexical rules can be integrated into the logical setup for hpsg provided by King (1989, 1994). We formalize a notation for lexical rules for use by linguists and define a rewrite system that takes this linguistic lexical rule notation into ordinary descriptions in King’s setup. These descriptions can then be interpreted in the usual way. As a result, we obtain a denotational semantics for the linguistic lexical rule notation defined.

The work presented here builds on the discussion of lexical rules in Meurers (1994) and especially the ideas developed in Meurers and Minnen (1995), where a computational treatment of lexical rules is proposed.

The presented research was sponsored by projects B4 and B8 of the Sonderforschungsbereich 340 of the Deutsche Forschungsgemeinschaft. I want to thank Thilo Götz, Erhard Hinrichs, Tilman Höhle, Paul King, Guido Minnen, Carl Pollard, Mike Calcagno, Bill Rounds and the participants of the hpsg Workshop (21– 23. June 1995, Tübingen, Germany) and the acquilex ii Workshop on Lexical Rules (9–11. August 1995, Cambridge, uk) for valuable comments and discussion. Of course, I am responsible for all remaining errors.

We start out with a discussion of what should be the formal basis of lexical rules. In section 3 we then discuss what lexical rules are supposed to do and which of these effects a linguist wants to write down explicitly and which remain implicit. In section 4 we then analyze what a linguistic lexical rule notation could look like and how the full intention of the linguist can be deduced, i.e., how a fully explicit description can be deduced from the lexical rule notation provided by the linguist. We then turn to the formal definition of a lexical rule notation along the lines discussed: Section 5.1 introduces the formal basis of hpsg we will be using, a version of the logic defined in King (1989). Section 5.2 defines the syntax of the linguistic lexical rule notation. In section 6 we then give a semantics of the linguistic lexical rule notation in terms of a rewrite system which transforms every lexical rule as specified by the linguist into an ordinary description, which can then be interpreted like any other description in King’s logic.

2 What should be the formal basis of lexical rules?

In traditional hpsg terms, a lexical rule is a pair of metadescriptions, one for each class of lexical entries related: “lexical rules must be seen as implicative relationships between lexical entries; but lexical entries themselves are constraints on feature structures (not feature structures themselves), so evidently a higher-order formalism must be developed within which such relationships can be expressed.” Pollard and Sag (1994, p. 395, fn. 1).

Some questions arise when taking a closer look at the implications of this. From a logical perspective, it seems questionable whether one really wants to extend the logical setup for hpsg by another level, just to formalize lexical rules. There are two other potential candidates for a metalevel formalization: the raising principle (cf., Pollard and Sag (1994, p. 140)) and the lexical template hierarchies (e.g., Pollard and Sag (1987, chapter 8)). However, the raising principle seems to be an instance of a more general principle ensuring full interpretation, and it has been argued that full interpretation should be a consequence of the logical setup, e.g., follow from the use of some kind of resource sensitive logic, not a consequence of explicitly formulated constraints.^{1} Regarding the second candidate, it seems to be possible to express the intention behind the lexical template hierarchies by regular type hierarchies and ordinary implicative constraints. Therefore, a kind of metalevel grouping of lexical descriptions is unnecessary. As a result, lexical rules appear to be the only remaining candidate for a metalevel formalization. However, current hpsg theories have a clear logical basis in the logic of King (1989, 1994) and we will show below that a functional equivalent of metalevel lexical rules can in fact be integrated in this setup without altering it.

A question regarding logical and linguistic issues concerns the intended status of a lexical entry serving as input to a lexical rule. The logical property of interest here is that it is undecidable whether a lexical entry which is intended to serve as input to a lexical rule is satisfiable with respect to a grammar, i.e., grammatical. A metalevel lexical rule therefore can derive grammatical entries from ungrammatical lexical entries as well as from grammatical ones.^{2} Or expressed differently, in general one cannot make sure that a metalevel lexical rule only applies to lexical entries having a non-empty denotation in the model of a grammar.^{3} To decide whether this is a positive or a negative consequence of a metalevel formalization, the exact consequences of this for linguistic theory will have to be discussed in some future work. In any case, it is a clear difference between a metalevel formalization and a description language formalization of lexical rules which we will pursue in this paper. Under a description language formalization such as the one introduced below, a lexical rule is an ordinary description which is only grammatical if each of its subdescriptions are grammatical. And one of these parts, the in-description, will only be grammatical if the conjunction of the indescription and a lexical entry is grammatical, as we will see in section 2.1. In other words, since a description language lexical rule relates sets of objects in the denotation of a theory, it has no access to ungrammatical objects. Note that this does not mean that under a description language formalization it is impossible to express that some lexical entry cannot be used unless it has undergone some lexical rule. Such ‘phantom’ lexical entries can be specified in a way which makes them unusable in a syntactic construction, but which does not keep them from being lexical entries which satisfy the grammatical constraints.

1Thanks to Erhard Hinrichs, Tilman Höhle and Carl Pollard for a clarifying discussion of this point.

2This was pointed out to me by Thilo Götz.

3Note that it is possible to specify metalevel lexical rules in such a way that they produce grammatical lexical entries only on the basis of grammatical ones. This is done by specifying the lexical rules to include the complete input in the output, e.g., by introducing an extra attribute in the output of the lexical rule to store the complete input in. However, since one of the motivations for a metalevel formalization of lexical rules is to avoid representing the source of the derivation of a lexical entry inside of the lexical entry, this possibility

Finally, from a linguistic point of view, we believe that it is questionable whether a formalization of lexical rules as metarelations corresponds to the most straightforward interpretation of the lexical rules recently proposed in the hpsg literature. For example, using lexical rules to perform operations on argument raised complements as proposed in many current hpsg theories for German, French, and Italian means that lexical rules treat information which is not part of the lexical entry, i.e., the input of a metalevel lexical rule. We therefore believe that it is more natural to think of these lexical rules as relating sets of fully specific word objects and not underspecified descriptions of these objects.

Due to these logical and linguistic questions arising under the traditional conception of lexical rules, we think it is worthwhile to see how far we can get with an alternative setup. Even though we agree with Pollard (1993) when he states that “[w]e want to be able to say in the logic: ‘every word must either satisfy one of the basic lexical entries, or else it must satisfy r_{i}(φ) [r_{i} being a lexical rule] for some i and some (not necessarily basic) lexical entry φ.”’, we disagree when he continues with: “Our representational formalism is too weak to express this, so it must be augmented further.” We will show that a mechanism which captures the full functionality of lexical rules as used in hpsg linguistics can be integrated into the logical setup for hpsg provided by King (1994) without having to enlarge the logic with a metalevel or extra notions such as copying or defaults.

In the following, we use the term “lexical rule” to refer to a mechanism such as the one formalized in this paper which provides the functionality which has been assumed for lexical rules in (recent) hpsg theories.

2.1 Lexical rules inside the logic

We see a lexical rule as a binary relation on the set of word objects. In general, there are several options for expressing relations. Either, one encodes the relations inside of the description language, or one expresses the relations by constructs which are part of the relational extension of the description language. Let us take a look at how lexical rule relations can enter the theory under these possibilities to formalize relations.

is not very attractive. Rather, Pollard (p.c.) pursues the idea that one does want to have lexical rules which derive grammatical entries out of ungrammatical input entries.

2.1.1 Lexical rules as description language mechanism

In an hpsg grammar, the lexicon is defined by an implicative constraint^{4} on objects of type word. The statement in figure 1 is sometimes referred to as the word principle. Implicative statements such as the word principle, which are part of the theory and have a type as antecedent, will be called type definitions in the following.

word → L_{1} ∨ … ∨ L_{n}

Figure 1: Defining a basic lexicon

There are several possibilities for introducing lexical rules into this setup of the lexicon. In general any relation can be encoded in the description language as a description of an object with one or more attributes. In hpsg, for example the immediate dominance schemata or the hfp and other principles express relations between a mother and one or more daughters. Copestake (1992), using a feature logic setup based on Carpenter (1992), makes use of this possibility to encode relations and defines a type lexical-rule with two attributes 0 and 1 having a type lex sign as appropriate values. Following a computational, rule-based approach, the type lexical-rule is defined as a subtype of rule and a parser uses lexical and non-lexical rules to build up structure. Since Copestake (1992, section 2.6.4), mostly for efficiency reasons, chooses a rule-based and not a constraint based setup like hpsg, she does not integrate the lexical rules into a word principle like the one shown in figure 1.

To integrate lexical rules into the word principle, an additional attribute (a so-called “junk slot”) needs to be introduced on objects of type word to house the lexical rule, or (in the alternative encoding described below) the second word related to. This junk slot technique for encoding (possibly recursive) relations on the level of the description language was first used by Aït-Kaci (1984). To formulate a word principle encoding a lexicon including lexical rules, the junk slot technique has for example been used in several implementations of hpsg grammars (Keller (1993), Kuhn (1993), Meurers (1993)).

Figure 2 shows a type definition for word, which defines an extended lexicon including lexical rules.

word → L_{1} ∨ … ∨ L_{n} ∨ 1 [STORE < \left[{OUT 1 \atop lex rule}\right] >]

Figure 2: An extended lexicon introducing basic entries and entries derived by lexical rules

The type word is assumed to have an additional appropriate feature store, the junk slot, which is list-valued. Furthermore, a new variety lex rule is introduced, having in and out as appropriate features with word values. The relevant part of the signature is shown in figure 3.

4We will use the term descriptions for the formulas of a formal language like the one of King (1989). The term specifications is used for this as well. The denotation of a description is the set of objects described.

Constraint will be used for those descriptions which are part of the theory (in a formal sense). Only those linguistic objects are grammatical that satisfy every description in the theory, i.e., every constraint. Speaking of terminology, we will use ⊤ as the least constraint type, ⊥ as the inconsistent type, and the term varieties is used to refer to most specific types, a variety is a type not having any subtypes apart from ⊥. The relevant formal definitions are provided in section 5.1.

⊤
[ \begin{matrix}& … & … \\ & STORE & list \\ word \end{matrix}]  [ \begin{matrix}& IN & word \\ & OUT & word \\ lex rule \end{matrix}] …

Figure 3: A signature for the modular lexical rule encoding

We will later refer to the setup introduced here as the modular lexical rule encoding, since it clearly separates the lexical rule descriptions from the lexical entries and the lexical rule objects from the word objects. The type definition for lex rule, in which the different lexical rules are specified, is given in figure 4.

lex rule →  [ \begin{matrix}& IN & D_{1} \\ & OUT & E_{1} \\ lex rule \end{matrix}] ∨ … ∨  [ \begin{matrix}& IN & D_{m} \\ & OUT & E_{m} \\ lex rule \end{matrix}]

Figure 4: Defining lexical rule objects in the modular encoding

So how does this encoding work? The type definition in figure 2 says that every object of type word is described by an ordinary lexical entry^{5} L_{i} (1 ≤ i ≤ n) or it is the value of the OUT attribute of a lex rule object. To relate the words described by out to other words, i.e., to express lexical rule relations, the in- and out-descriptions d_{j} and e_{j} (1 ≤ j ≤ m), abbreviated as lr-in and lr-out, need to be specified. One disjunct on the right-hand side of the implication in figure 4 encodes one lexical rule, which are abbreviated as lr. To state that certain properties of both sets of word objects related are identical, path equalities between lr-in and lr-out are specified. Note that the appropriateness conditions for lex rule ensure that the value of the in feature is of type word. It therefore has to satisfy the type definition for word, i.e., one of the lexical entries of figure 2. Naturally the lexical entry satisfied can again be the last disjunct, i.e., the output of a lexical rule.

Note that the description of the last disjunct, i.e., the special entry, in figure 2 is a cyclic structure. Even though this is not necessarily problematic, an alternative encoding of a lexicon with lexical rules avoiding cyclic structures is possible. Two subtypes of word, say simple-word and derived-word, can be introduced with derived-word having an additional appropriate attribute in with word value.

⊤
\left[{. . . . . . \atop word}\right]  …
simple word  \left[{IN word \atop derived word}\right]

Figure 5: The signature for the word-in-word encoding of lrs The following type definitions then define the lexicon including lexical rules:

5For cleanness sake, in ordinary lexical entries the junk slot STORE should be assigned e list as value.

simple-word → L_{1} ∨ … ∨ L_{n}
derived-word → ([IN D_{1}]∧E_{1}) ∨ … ∨ ([IN D_{m}]∧E_{m})

Figure 6: The theory for the word-in-word encoding

In this encoding, the in-description D_{j} of a lexical rule j (1 ≤ j ≤ m) is specified on the in-attribute, while the out-description E_{j} is specified directly on the derived-word. This eliminates the structure sharing we needed in the modular lexical rule encoding.

2.1.2 Lexical rules as ‘proper’ relations

If we chose a formal language for hpsg which allows us to use the relational extension within descriptions, such as the relations defined in Götz (1995) building on King (1989), Höhfeld and Smolka (1988), and Dörre (1994), the proposals for representing a lexicon including lexical rules discussed in section 2.1.1 above can be expressed without having to introduce lexical rules or derived words as types. The lexicon with added lexical rules of figure 2 in a version with lexical rules expressed by ‘proper’ relations looks as follows.

word → L_{1} ∨ … ∨ L_{n} ∨ lex rule(word)

Figure 7: A lexicon with added lexical rule relations

lex rule(D_{1}) := E_{1}.
⋮
lex rule(D_{m}) := E_{m}.

Figure 8: Defining the lexical rule relation

Note that a functional notation of relations is used, since this way ordinary descriptions and relations will have the same denotation, a set of objects. Just as before, D_{j} is the indescription of lexical rule j and E_{j} its out-description. What is different in this encoding is that now the lexical rules are defined on a different level than the word objects. Which word objects satisfy our theory is defined using the description language, while the lex rule relation is defined using the relational extension of that description language.

2.1.3 Which representation of lexical rule relations should we use?

Having introduced three possibilities for representing lexical rules within the logic, we need to pick one as the basis of our formalization of lexical rules.

Since one of the aims of our work is to show that lexical rules can be formalized in a standard logic for hpsg, we will introduce lexical rules as types, and not as ‘proper’ relations in the way discussed in the last section. Even though introducing lexical rules in the universe of linguistic objects might be unappealing from a philosophical point of view, there also are some advantages to encoding lexical rules as types. First of all such an encoding allows us to hierarchically organize lexical rules, which makes it possible to express generalizations over groups of lexical rules in a straightforward way. For example, Hinrichs and Nakazawa (1994) say that the Partial-VP Topicalization Lexical Rule, the Split-NP Topicalization Lexical Rule, and the Split-NP Topicalization Lexical Rule 2 share a common mechanism. However, without a possibility to hierarchically group lexical rules and formulate constraints on these groups, they are unable to express the general properties shared by these three rules in any formal way. Apart from such groupings of lexical rules to express common properties of certain subgroups, there also seems to be a clear need to constrain lexical rules in general in a principled way, just like the universal principles of hpsg constrain the rest of the grammar. When lexical rules are introduced as types, constraints on lexical rules can be expressed like any other principle by adding the appropriate implicative description to the theory. Apart from these formal arguments, there also are some interesting linguistic consequences of the fact that under the modular and the word-in-word encoding a word contains its full derivation history, i.e., those words it was derived from by a lexical rule. Just to give an example, one possibility this opens up is to have the binding theory operate on the valence lists of a word before extraction lexical rules have applied. This would eliminate the need of a separate arg-s list for the sake of the binding theory.^{6}

Summing up, it seems to be the case that apart from our original motivation to use the standard logical basis of hpsg, there also are some other interesting aspects of the wordin-word and the modular encoding of lexical rules which make it worthwhile to try and use one of the two encodings in the following. Having decided for a pure description language representation, we still need to choose between the modular and the word-in-word approach. Here a choice is hard to motivate, since both encodings are rather similar and little seems to depend on a choice. Since the modular description language encoding (figures 2, 3, and 4) has the advantage of clearly separating lexical rules and their in- and out-descriptions from words, we will use it, rather than the second in the rest of the paper.

Note that nothing of real importance to the formalization of a lexical rule notation in the next sections depends on the choice made here. The idea behind the lexical rule notation discussed and formalized in the following sections can (presumably) be used for any kind of representation of lexical rules as relations. In fact, even when a metalevel representation of lexical rules is used, some of the discussion of how lexical rules should be noted and how that notation is interpreted should carry over. The reader interested in a metalevel formalization of lexical rules is referred to (Calcagno, 1995) and (Calcagno and Pollard, 1995).

3 Lexical rules and linguistic specifications

Now that we have explored possible ways to formalize lexical rules as ordinary constraints, one could think that we’re done. Using the modular lexical rule encoding, the linguist can specify lexical rules as a constraint on lex rule and the theory will do what it’s supposed to. However, explicitly having to specify everything a lexical rule is intended to do, does not really correspond to what hpsg linguists are used to. Instead, one usually only writes down those things which really matter for what the lexical rule is intended to do. The rest stays implicit and is to be inferred from what is said. So, even though in the last section we found a way to write down fully explicit lexical rule relations so that they are interpreted as intended, we still have to go one step further: We need to develop a notation in which linguists can write down lexical rules in an elegant way which leaves some things implicit as long as they can be inferred. Once we know what such a linguistic lexical rule notation (llr-n) should look like, we need to show how lexical rules specified in llr-n are translated to constraints on lex rule. The rest of the paper serves to explore and formalize these two steps.

6This idea is due to Tilman Höhle.

To avoid possible confusion here, let us repeat that we distinguish the language used by the linguist to write down a lexical rule (leaving some things implicit) from the explicit description of what the lexical rule is intended to do. The first will be called linguistic lexical rule notation (llr-n) and it will be explored and formally defined in the following sections. For the second, the explicit descriptions, the ordinary descriptions of the formal language of King are be used. Lexical rules as specified by the linguist are abbreviated as llr and they are written as shown in figure 9. The in- and the out-description llr-in and llr-out can be written down in a slightly extended version of avms in which we allow two additional symbols that will be introduced below: ♭ and ♯. In order to distinguish the augmented language used by linguists to specify llrs from the ordinary description language, we will call the expressions used in llrs linguistic descriptions or l-descriptions.

llr-in ↦ llr-out

Figure 9: A notation for linguistic lexical rules (llrs)

Fully explicit descriptions of lexical rule objects are abbreviated as lr and they are written in the formal language of King or in an avm notation as shown in figure 10.^{7}

[ \begin{matrix}& IN & lr-in \\ & OUT & lr-out \\ lex rule \end{matrix}]

Figure 10: A notation for lexical rules (lrs)

We start with a brief overview of what explicit lexical rule relations are intended to do.

3.1 What needs to be expressed?

Consider two word objects related by a lexical rule. We can distinguish three parts:

a) Certain properties of one object are related to different properties of the other object,

b) certain properties of one object are related to identical properties in the other object, and

c) certain properties of one object have no relation to properties of the other object, either because

i. the linguist wants certain properties to be unrelated, or because

ii. certain properties are appropriate for one object but not the other.

For example, a lexical rule relating German base form verbs to their finite forms, among other things needs to

a) relate the base verb form specification and the base morphology to a finite verb form and the corresponding finite morphology, b) ensure that the semantic predicate expressed is the same for both objects, and

7Note that avms are used in in an augmented variant in llrs and in the standard way in lrs since they are a convenient notation. Nonetheless one should bear in mind that there is a difference between llrs and lrs.

The first is an abbreviation of the second and it does not make sense to interpret llrs directly as descriptions in King’s setup.

c) i. ensure that the finite verb can appear in inverted or non-inverted position regardless of the inversion property of the base verb (which in fact can only occur in non-inverted position).

An example for the case c-ii.), where certain properties cannot be transferred, could occur in a nominalization lexical rule which relates verbs to nouns. Since verb form is inappropriate for nouns, that specification cannot be transferred from the verb.

Regarding terminology, following Meurers and Minnen (1995) we will refer to the the task of descriptions ensuring that certain properties are identical (case b) as property transfer.

Now we’re ready to explore how the three cases a), b), and c) are explicitly or implicitly expressed in a notation which a linguist can use to write down lexical rules (llr-n).

3.2 What needs to be written down?

When writing down a lexical rule, the linguist only needs two express two of of the three cases (relating differing properties, relating identical properties, unrelated properties). When the linguist specifies those properties which are intended to differ (a) and one more case (b or c), the third kind can be deduced; i.e., it does not have to be expressed explicitly and could be called the “default” specification of lexical rules (in a non-technical sense). So there are two possibilities here: either we have a llr-n in which those properties which are intended to be identical in the objects described by lr-in and lr-out (case b) are explicitly mentioned. Then non-related properties can remain unexpressed. Or we have a llr-n in which we explicitly have to mention those properties which are intended to be unrelated in the objects described by lr-in and lr-out (case c-i.). In that case identical properties can remain implicit.

3.2.1 Leaving non-relatedness (case c-i.) unexpressed

At first sight it might seem natural to ask the linguist to express in a lexical rule those specifications which relate properties, i.e., cases a) and b), and keep unexpressed which parts of the objects are unrelated (case c). However, in highly lexicalized theories like hpsg a lexical entry contains many specifications of which only few are relevant in a specific lexical rule. Asking the linguist to explicitly specify that all those specifications without relevance to the lexical rule are identical in the objects related (in case they are appropriate) therefore would amount to asking for a lexical rule with many specifications which are of no direct importance to what the lexical rule is intended to do.

Furthermore, specifying all identities by hand sometimes can only be achieved by splitting up a lexical rule into several instances.^{8} Let us illustrate this with an example based on the signature given in the appendix of Pollard and Sag (1994). Assume, for expository purpose only, a lexical rule deriving predicative signs from non-predicative ones.

[SYNSEM|LOCAL|CAT|HEAD|PRD -] ↦ [SYNSEM|LOCAL|CAT|HEAD|PRD +]

Figure 11: prd-llr (for exposition only)

A linguist having to specify property transfer by hand would be forced to write down five different rules, one for each subtype of the substantive heads (those which can have a PRD attribute). There are two reasons why one needs to split up the rule for each subtype if one explicitly specifies property transfer. First, the subtype of substantive needs to be preserved, but no path equality can be specified since the attribute PRD which gets changed is below that type. Second, the subtypes have different appropriate attributes for which we need to make sure that they are transferred. Figure 12 shows one of the five lexical rules a linguist would have to write to explicitly write down property transfer, the one for verbs.

8Cf., Meurers (1994, section 4.1.3) and Meurers and Minnen (1995).

[\begin{matrix}PHON & 1 \\ SYNSEM & [\begin{matrix}LOCAL & [\begin{matrix}CAT & [\begin{matrix}HEAD & & [ \begin{matrix}& PRD & - \\ & VFORM & 2 \\ & AUX & 3 \\ & INV & 4 \\ verb \end{matrix} ] \\ SUBCAT & 5 \\ MARKING & 6 \end{matrix}] \\ CONT & 7 \\ CONX & 8 \end{matrix}] \\ NONLOCAL & 9 \end{matrix}] \\ QSTORE & 10 \\ RETRIEVED & 11 \end{matrix}] ↦

PHON  1

SYNSEM  [\begin{matrix}LOCAL & [\begin{matrix}CAT & [\begin{matrix}HEAD & & [ \begin{matrix}& PRD & + \\ & VFORM & 2 \\ & AUX & 3 \\ & INV & 4 \\ verb \end{matrix}] \\ SUBCAT & 5 \\ MARKING & 6 \end{matrix}] \\ CONT & 7 \\ CONX & 8 \end{matrix}] \\ NONLOCAL & 9 \end{matrix}]

QSTORE  10
RETRIEVED 11

Figure 12: prd-llr with property transfer for verbs explicitly specified

It is clear that we do not want to ask the linguist to write down several instances of lexical rules in this way. But let us briefly note that the above example points out an important property of llrs which will be very useful when we explain how llrs are transformed into explicit lrs: it suffices to look at a llr and the signature to determine which kind of objects could undergo this lexical rule in order to tell which attributes need to be transferred. No reference to lexical entries was necessary to make property transfer in the above example explicit. We only need lexical entries when an explicit lexical rule is applied to make sure that the objects satisfying the input of a lexical rule also satisfy a basic lexical entry or the output of a lexical rule. As we saw in section 2.1, figure 2, the word principle is extended to take care of this.

3.2.2 Leaving identity (case b) unexpressed

The notation for lexical rules used in most hpsg theories proposed in the literature assumes that the properties which are not explicitly changed by the lexical rule, are identical for both sets of objects related. In other words, property transfer (case b) is left unspecified.

The advantages of allowing the linguist to leave identities unexpressed follow from the disadvantages discussed in section 3.2.1 above: Firstly, the linguist only needs to express those things of direct relevance to the lexical rule. Secondly, leaving identities unexpressed saves the linguist from having to split up a lexical rule into several instances. And finally, since we are striving to provide a semantics for lexical rules as used in hpsg linguistics, as long as it is formally reasonable, we naturally try to get as close as possible to the notation assumed in the hpsg theories proposed in the literature.

Nothing was said so far about how the linguist expresses case c) and in fact this case is usually not mentioned in the hpsg literature. However, if both case b) and c) are left unspecified, it is not possible to uniquely determine whether a property of one object is supposed to be identical to that of the other object or whether that property of both objects is unrelated. To distinguish between the two cases we will need to introduce some additional notation for case c).

3.2.3 A linguistic lexical rule notation

In the last two sections we discussed two possible setups for a llr-n and we decided that we do not want to express property transfer explicitly in the llr-n. So now the task is to fix a syntax for the other two cases.

The case a) in which the linguist specifies which properties are changed is the easiest case. Here everything is already explicit and we can use the ordinary descriptions of the formal language of King. Case c-ii.) doesn’t need any additional notation since it only amounts to saying that no inappropriate (in the technical sense) property transfer should be deduced.

So far nothing apart from ordinary descriptions was required. In fact, one could try to also express case c-i.), the intentional non-correspondence, by using certain ordinary descriptions, namely denotationally irrelevant ones. To specify that the type value of an attribute in the out-description is intended to be unrelated to the in-description, one could specify a type as value of that attributes which is less specific than the type which is appropriate for that attribute. However, since the appropriate value of an attribute depends on the type of object this attribute is on, and the intended interaction of types in the in- and out-description is already rather complex (cf., section 4.1), it seems clearer to introduce a separate notation for type unrelatedness here.

In a description language using variables instead of path-equalities, there also is a possibility to express that two attributes are not required to be reentrant (called reentrancy elimination in the following) using a denotationally irrelevant description. By using a variable as value of an llr-out attribute which is different from the variable that is the value of its corresponding llr-in attribute, one can express that the llr-out attribute is not intended to be reentrant with its corresponding llr-in attribute and the nodes it is reentrant with.^{9} In case the llr-out attribute is no longer reentrant with any other node, the new variable will only have a single occurrence. However, proceeding in this way has the consequence that llrs can no longer be mapped to lrs just by looking at the signature. Instead one would have to consider which kind of variables are present in the lexical entries that license word objects which can undergo a lexical rule. Since otherwise we are able to map llrs into explicit lrs just by looking at the llrs and the signature, having to look at other parts of the grammar to tell what the abbreviating notation means seems to be an unnecessary complication.

9I believe this possibility was mentioned by Mike Calcagno in a talk on 23. June 1994 at the hpsg Workshop in Tübingen.

After this excursion into the possibilities to express case c-ii.) without adding additional llr notation, we now show how extra llr syntax can be introduced to do the job. Note that we do not extend the description language at the formal basis of hpsg, i.e., the King logic. We only add additional notation to the linguistic lexical rule notation which will be used by the procedure which maps llrs into lrs. The mapping will also eliminate the extra notation so that it does not have to be interpreted in lrs.

Type elimination is noted by a ♭ as value of a type assignment. E.g., [_{X|U} _{♭}] is used to eliminate the value of attribute U.

Regarding path equality elimination, one might be tempted to introduce ♯ as a binary operator which is used just like path equality ≈. The notation with different subscripts, i.e., ♯_{i}, could then be used if multiple pairs of path equalities are to be eliminated. However, there is a problem with such a notation. Take the llr given in 13.

[\begin{matrix}W & 1 \\ X & 1 \\ Y & 1 \\ Z & 1 \end{matrix} ] ↦ [\begin{matrix}W & ♯_{2} \\ X & ♯_{2} \end{matrix}]

Figure 13: A llr with the binary ♯ notation

Take the set of objects described by llr-in.^{10} llr-out is intended to say that there is a second set of objects, which is just like the first set but we don’t want to force attributes W and X to be token identical for the second set of objects. However, because of the transitivity of path equality, having to eliminate the path equality restriction on W and X also requires us to alter the relationships of W and X to Y and Z. So it is unclear whether the lr which is abbreviated by the llr in 13 is supposed to be the description in 14 a, b, c, or d.

a. [\begin{matrix}IN & [\begin{matrix}W & 1 \\ X & 1 \\ Y & 1 \\ Z & 1 \end{matrix} ] \\ OUT & [\begin{matrix}W & 1 \\ X & 2 \\ Y & 1 \\ Z & 2 \end{matrix} ] \end{matrix}]  b. [\begin{matrix}IN & [\begin{matrix}W & 1 \\ X & 1 \\ Y & 1 \\ Z & 1 \end{matrix} ] \\ OUT & [\begin{matrix}W & 2 \\ X & 1 \\ Y & 1 \\ Z & 2 \end{matrix} ] \end{matrix}]  c. [\begin{matrix}IN & [\begin{matrix}W & 1 \\ X & 1 \\ Y & 1 \\ Z & 1 \end{matrix} ] \\ OUT & [\begin{matrix}W & 1 \\ X & 2 \\ Y & 1 \\ Z & 1 \end{matrix} ] \end{matrix}]  d. [\begin{matrix}IN & [\begin{matrix}W & 1 \\ X & 1 \\ Y & 1 \\ Z & 1 \end{matrix} ] \\ OUT & [\begin{matrix}W & 2 \\ X & 1 \\ Y & 1 \\ Z & 1 \end{matrix} ] \end{matrix}]

Figure 14: The four possibilities to map the llr of figure 13 into a lr

To obtain a unique interpretation of the binary ♯ notation one would need to complicate the ♯ notation further or specify additional rules for its interpretation. Instead of complicating matters in this way, we introduce path equality elimination ♯ as eliminating the path equality requirements with one path only. Figure 15 shows the avm notation for eliminating the path equality requirements on attribute X.

10Note that the objects in the denotation of llr-in in the modular lexical rule encoding also have to satisfy a lexical entry or the output of a lexical rule. The token identity requirement on the objects therefore can stem from either of these places. Since we want to rewrite a llr as lrs independent of the lexical entries, we therefore cannot look at which path equalities hold between attributes in the input and do something on the basis of that. Instead, we use structure sharing between attributes in the in- and the out-specification which is possible since the signature tells us what attributes can be present. This will be discussed in section 4.1.3.

[X ♯]

Figure 15: Path equality elimination in avm notation

In a sense, the unary ♯ notation is less expressive that the binary one. If one wants to specify an llr-out for the llr-in of figure 13 so that the llr-out is rewritten as either one of the four specific cases of figure 14, the path equalities which are intended to be kept for an attribute for which ♯ was used to eliminate some path equalities need to be restated. It is necessary to repeat certain path equalities because it is only possible to eliminate all path equalities with an attribute and not only those holding between two attributes leaving the others as in the binary notation. Still, the notation seems to be straightforward and until there is evidence that a more expressive notation is needed we will stick to it.

a. [\begin{matrix}X & ♯ 2 \\ Z & 2 \end{matrix} ]  b. [\begin{matrix}X & ♯ 1 \\ Y & 1 \end{matrix} ]  c. [X ♯]  d. [W ♯]

Figure 16: llr-outs which are used to arrive at the cases in figure 14 with a unary ♯

4 Exploring a linguistic lexical rule notation

Now that we have an idea of what we need in a llr-n, in the following we need to explore how the l-descriptions making up the llr-n can be used in a way that makes it possible to deduce the intended explicit lexical rule descriptions.

The idea behind our formalization of a linguistic rule notation is to define a rewrite system that takes every llr-n into fully specified lexical rule descriptions which can be given the standard set theoretical interpretation defined by King (1989). What exactly has to be done by this rewrite system? The mapping from llrs to lrs has to fill in descriptions ensuring identity of unmentioned properties (property transfer) and this has to be done with respect to the extra notation added to the llr-n to express unrelatedness (case c-i). We will call this enriching an llr. The result of enriching an llr is a lr. In terms of the description language encoding we use, enriching adds variety assignments to lr-out and path equalities between paths in the in-description and the corresponding paths in the out-description.

As became clear when we discussed the different setups for a llr-n in the last section, enriching is done solely on the basis of the llrs and the signature; it is not dependent on the lexical entries. Since llrs are interpreted by enriching them into ordinary lr descriptions and interpreting these in the ordinary set theoretical way this allows us to assign a semantics to llrs without looking at the lexical entries in a grammar. What makes this possible is the closed world interpretation of type hierarchies assumed in hpsg and King (1989). The signature and the closed world assumption tell us which kind of word objects could possibly exist (regardless of whether they are grammatical, i.e., in the denotation of the theory, or not). We already saw the closed world assumption at work in figure 12 of section 3.2.2 when we discussed what a linguist has to do if (s)he wants to specify property transfer by hand. In what follows, we use the same logical properties of hpsg to automatically enrich a description with property transfer.

4.1 Exploring the various possibilities

There are two basic types of specifications: variety assignment (∼) and path equality (≈). Since we are dealing with two descriptions, one as part of the llr-out, one as part of llr-in, the relative position of two specifications needs to be considered. The path leading to the specification in llr-out can be included in that leading to a specification in llr-in. The two specifications can be at the same place in llr-in and llr-out. The path leading to the specification in llr-out can be an extension of that leading to a specification in llr-in. To deal with the l-description syntax we allowed for llr-out, we additionally have to consider certain out-descriptions: the empty specification, the type elimination specification (♭), and the path equality elimination specification (♯).

As basis of the examples discussed below, assume the following example signature:

⊤
[ \begin{matrix}& X & a \\ & … & … \\ word \end{matrix} ]  [ \begin{matrix}& U & bool \\ & V & bool \\ a \end{matrix}]  bool  …
a_{1}  a_{2}  + −
\left[{V + \atop a′_{1}}\right]  a′_{2}  \left[{W bool \atop a′′_{2}}\right]

Figure 17: An example signature

4.1.1 What’s the type when type meets type?

Consider the linguistic lexical rules shown in figure 18.

\begin{matrix}1. & word ↦ [X a_{2}] \\ 2. & word ↦ [X a′_{2}] \end{matrix}

Figure 18: llrs with type specifications

We know by the signature that every word object that serves as input to one of these lexical rules has to have an X attribute that has some variety of a as its value. So what kind of X value do we want for the word objects that are related to the first set by one of the lexical rules in figure 18? One thing is clear: we want the objects licensed by the output of the lexical rule to be in the denotation of [_{X} _{a_{2}}] for the first and [_{X} _{a′_{2}}] for the second lexical rule. What needs to be decided in addition to that is whether the set of objects is further restricted to have the value of X identical to the value of X in an object which serves as input to the lexical rule. Say, for example a word object whose X is a′_{2} serves as input to the first lexical rule. Are there only objects in the denotation of the output of the lexical rule that have a′_{2} as value of X in that case, or are there also some that have a′′_{2} as value of X (which would be in the denotation of [_{X} _{a_{2}}]). Generally speaking, in the first case a type on an object undergoing a lexical rule is preserved if it is compatible with the out-specification. In the second case, the out-specification is all that matters. Say we pursue the first possibility and do preserve the type. Then, in cases where preservation of a type is not intended, adding a single type elimination specification to llr-out does the trick. So this is ok. On the other hand, if we do not preserve the type, having to specify transfer of the type specification by hand can force the linguist to explicitly specify many subcases of the llr, as was discussed in section 3.2.1. As a result, a llr-n designed to preserve a type if possible seems to be the most convenient.

LLR-N design decision 1 For every path P with value t in llr-out which is also defined on the objects in the denotation of llr-in do the following in case there is no specification [_{P} _{♭}]: specify the lrs so that each object having a subtype of t as value of P is related to objects having the same variety as P’s value. Every other object (the value of P is not described by t) is related to objects having any subtype of t as value of P.

The effect of this design decision is that every llr is enriched into several lrs: we obtain one lr for every variety assignment possible according to the signature and the specification in llr-out.

Applying the design decision 1 to the llrs in figure 18, we obtain the following. The cases in which a variety is preserved are marked with a •. In the other cases, the variety considered in lr-in and the type in llr-out is incompatible and the specification in llr-out is used for lr-out.

1. a) [\begin{matrix}IN & [X a′_{2}] \\ OUT & [X a′_{2}] \end{matrix}] •

b) [\begin{matrix}IN & [X a′′_{2}] \\ OUT & [X a′′_{2}] \end{matrix}] •
c) [\begin{matrix}IN & [X a′_{1}] \\ OUT & [X a_{2}] \end{matrix}]

2. a) [\begin{matrix}IN & [X a′_{2}] \\ OUT & [X a′_{2}] \end{matrix}] •

b) [\begin{matrix}IN & [X a′′_{2}] \\ OUT & [X a′_{2}] \end{matrix}]
c) [\begin{matrix}IN & [X a′_{1}] \\ OUT & [X a′_{2}] \end{matrix}]

Figure 19: lrs resulting from enriching the llrs of figure 18

So far, so good; but what about the following cases:

\begin{matrix}1. & word ↦ [X|W +] \\ 2. & word ↦ [X|V −] \\ 3. & word ↦ [X [\begin{matrix}U & 1 − \\ V & 1 \end{matrix}]] \end{matrix}

Figure 20: llrs with implicit type specifications

The problem is that in the examples in figure 20, even though no type is specified directly in llr-out for X, still only certain types as values for X in llr-out will yield a consistent description. In the first llr in figure 20, the attribute W is only appropriate for objects of type a′′_{2}, in the second llr the attribute V with value “−” is not appropriate for objects of type a′_{1}, and in the third llr V is structure shared with U and, since U has “−” as value, again a′_{1} is not a possible value for X.

The solution to this problem is to first infer the types on all nodes in llr-out which are forced by the descriptions in llr-out and the signature. Then the ordinary design decision 1 can be used. Luckily, the task of inferring a variety as value of each attribute in a description has already been dealt with: The normalization algorithm of Götz (1993) and Kepser (1994) can be used to transform a description into a normal form representation in which (among other things) every attribute is assigned a variety consistent with the rest of the description (in case this is possible). The formal definition of the normal form is provided in section 5.3.

4.1.2 Paths not mentioned in the out-specification

Having dealt with type specifications, we now look at attributes which do not occur in llrout even though they could be there according to the signature. In case such an attribute is also appropriate for llr-in, we can transfer the value of the attribute in llr-in to the corresponding attribute in llr-out. In our setup this is done by specifying a path equality between the path in llr-in and the corresponding one in llr-out. Having such a path equality do the property transfer makes sure that all constraints on the path which have to be satisfied by an object serving as input to the lexical rule – some of which stem from lr-in, others that aren’t present in the lexical rule but stem from a lexical entry or output of another lexical rule – are present on the corresponding path in lr-out.

Two other things should be explained here: First, we know that if there is a path equality between two paths this means that both paths point to the same object. Therefore we also know that the value of an appropriate attribute A extending one of the paths in the path equality and the value of the same attribute A extending the other path in the path equality will also be token identical. As a result, it suffices to specify structure sharing at certain attributes as close as possible to the root, namely those attributes which do not occur in llrout themselves, but directly extend paths or subpaths that are specified in llr-out. Note that since the number of specifications in llr-out is finite and the number of appropriate attributes of an object is finite, a finite number of path equalities between llr-in and llrout will suffice to specify property transfer of unmentioned attributes. Second, as we saw in section 3.2.1, one needs to watch out for subtypes of llr-out attribute values which have additional appropriate attributes. But since in the formal setup of King (1989) introduced in section 5.1 a type assignment is only an abbreviation for a disjunction of variety assignments and since we will deduce property transfer on the basis of a disjunctive normal form, all cases including those introducing additional appropriate attributes are explicit and nothing special needs to be done. The following design decision does the trick.

LLR-N design decision 2 Take any path P that occurs in llr-out. For each appropriate attribute A s.t. PA does not occur in llr-out, lr contains a path equality between PA in lr-out and PA in lr-in in case A is appropriate for the corresponding path P in lr-in.

Since different varieties as value of A can have different appropriate attributes, the above design decision tells us to map every llr into a set of lrs just like it was the case in the type– type case dealt with in design decision 1. The resulting set of lrs is interpreted disjunctively. Each lr has a specific variety as value of A and in that rule the attributes appropriate for that variety are dealt with. We already saw an example for the effect of this design decision in section 3.2.1. Decision 2 states that figure 11 on p. 9 is interpreted as if it had the structure sharings defined in 12 on p. 10 specified. So by interpreting llrs in the way fixed in design decisions 2 and 1, we have indeed automated what in section 3.2.1 we argued that we do not want to ask the linguist to do by hand.

4.1.3 The case of path equalities

After having decided what we do with unspecified attributes and type specifications, we now turn to path equalities. The first idea one might have is to look at the path equalities in llr-in and transfer them to the corresponding paths in llr-out. For example, if paths X and Y are structure shared in llr-in then we include a structure sharing between X and Y in lr-out, unless one of the paths in llr-out carries a path equality elimination specification ♯. However, such a straightforward copying of path equalities can be problematic: Höhle (1995) shows that preserving path equalities in such a way leads to wrong results when using the Complement Extraction Lexical Rule of Pollard and Sag (1994) to extract complements from verbs bearing a Hinrichs/Nakazawa style argument raising specification. The reason has to do with the first-rest encoding of lists and the fact that a path equality cause two list positions to be structure shared, not two list elements. As a result, if one element of a list is removed in llr-out, the path equalities of llr-in would have to be adjusted before copying them over to llr-out, to reflect the new position of the elements which were structure shared before. While such adjusting of path equalities already is a complicated, in the general case perhaps impossible task, there even is one more complication. Since consistency is assumed as application criterion, one not only has to take care of the path equalities in llr-in but also the path equalities which occur in the lexical entries the lexical rule applies to. Note that it is not possible to determine a finite set of path equalities just by looking at the signature and the lexical rule, as was the case when we had to find out above what variety specifications or paths might occur in some kind of lexical entry. So if we pursue this idea of copying over (adjusted) path equalities, we can no longer interpret lexical rules independent of the lexical entries. I.e., in such a case it is not possible to transform the linguistic lexical rules into an explicit, interpretable form just by looking at the linguistic lexical rule and the signature.

Luckily, there is an alternative. Instead of taking path equalities form the input and enforcing corresponding path equalities in the output, we specify path equalities between llr-in and llr-out. For example^{11}, when llr-in contains the path equality (IN|X = IN|Y), we do not add the path equality (OUT|X = OUT|Y); instead we add (IN|X = OUT|X) and (IN|Y = OUT|Y). The path equality (OUT|X = OUT|Y) then does not have to be explicitly stated since it follows by transitivity of the path equality relation. Under such a setup, we need to watch out for one thing though: We introduce path equalities between paths in lrin and lr-out. So any specification of a path structure shared with in lr-out will also restrict the corresponding path structure shared with in lr-in. By specifying path equalities for transfer in such a case, we therefore restrict the domain of objects which can undergo the lexical rule; an unwanted effect. We will therefore only transfer path equalities for those paths, that do not get specified in llr-out. Since this is just what we did in design decision 2, there’s nothing else to do here.

LLR-N design decision 3 The transfer of path equalities is ensured by design decision 2.

Before we finish this section, one might think that we still need to cover several other cases. In the very beginning of this section we said that the relative position of two specifications needs to be considered; but so far we seem not to have addressed specifications which are not on the same attribute in llr-in and llr-out. So how does a path equality or type specification on an attribute in llr-in interact with a path equality or type specification on a different attribute in llr-out when it comes to enriching? In fact, this question was already answered above, but let us clarify the issue some further. Regarding the treatment of types, design decision 1 only treat types as values of the same attribute in llr-in and llr-out; but the trick is that we normalize the l-descriptions first. After normalizing a description, we know for every path which varieties are possible values that are consistent with the rest of the description. Therefore design decision 1 does all there is to do. Regarding the treatment of path equalities, design decision 2 specifies path equalities between lr-in and lr-out for paths which are not specified in lr-out. The structure sharing between in- and out-description ‘automatically’ lets the attribute in llr-out take part in whatever restrictions are put on objects described by lr-in, e.g., when the lr is applied. So we don’t need to worry about descriptions in lr-in. And since we only specify such transfer structure sharing for paths which are not part of llr-out, we do not need to worry about other specifications in llr-out either.

11We use a somewhat informal notation here since the formal notation will be introduced in the following section 5.1.

Now that we’ve cast our intuitions into the design of a language to be used by linguists to specify lexical rules (llr-n), we need to formalize these intuitions.

5 The formal languages

5.1 The description language of King (1989)

As the formal basis of our approach we assume the logical setup of King (1989). As shown in King (1994), this setup provides the foundation desired for hpsg in Pollard and Sag (1994). The formal language defined in the following is a version of the one proposed by King.

5.1.1 Syntax

Definition 1 (Signature) A signature S is a triple ⟨V, A, approp⟩ s.t.

• A is a finite set of attribute names

• V is a finite set of varieties (also called species or minimal types)^{12}

• approp : V ×A → P ow(V) is a total function from pairs of varieties and attribute names to sets of varieties

Everything which follows is done with respect to a signature. For notational convenience we will work with an implicit signature ⟨V, A, approp⟩. This is possible since at no point in our proposal do we have to alter the signature.

Definition 2 (Term) Let : be a reserved symbol, the root symbol of a path. A term is a member of the smallest set T s.t.

• : ∈ T and

• τα ∈ T if τ ∈ T and α ∈ A

Definition 3 (Description) Let (,), ∼, ≈, ¬, ∧, ∨ and → be reserved symbols. A description is a member of the smallest set D s.t.

• τ ∼ φ ∈ D if τ ∈ T and φ ∈ V

• τ_{1} ≈ τ_{2} ∈ D if τ_{1}, τ_{2} ∈ T

• ¬δ ∈ D if δ ∈ D

12For easier comparison with standard hpsg notation, one can introduce a finite join semi-lattice ⟨Z, ⪯⟩ as type hierarchy with Z ⊃ V. A type assignment is then simply an abbreviation for a set of variety assignments:

τ ∼ t = ⋁{τ ∼ φ | φ ⪯ t} with τ ∈ T , t ∈ Z, and φ ∈ V. In the paper, we assume every type assignment to be expanded in that way. Nothing of theoretical importance hinges on this.

• (δ_{1} ∧ δ_{2}), (δ_{1} ∨ δ_{2}), (δ_{1} → δ_{2}) ∈ D if δ_{1}, δ_{2} ∈ D Definition 4 (Theory) A theory Θ is a subset of D (Θ ⊆ D). Definition 5 (Set of Literals) A set of literals Σ is a subset of the set of descriptions D (Σ ⊂ D), s.t. each δ ∈ Σ has one of the four forms (τ, τ_{1}, τ_{2} ∈ T ; φ ∈ V):

• τ ∼ φ

• τ_{1} ≈ τ_{2}

• ¬ τ ∼ φ

• ¬ τ_{1} ≈ τ_{2}

5.1.2 Semantics Definition 6 (Interpretation of a Signature) An interpretation I is a triple ⟨U, V, A⟩ s.t.

• U is a set of objects, the domain of I,

• V : U → V is a total function from the set of objects to the set of varieties, the variety assignment function,

• A : A → {U⇀U}^{13} is an attribute interpretation function s.t. for each u ∈ U and

α ∈ A:

– if A(α)(u) is defined then V(A(α)(u)) ∈ approp(V(u), α), and – if approp(V(u), α) ≠ ∅ then A(α)(u) is defined.

Definition 7 (Interpretation of Terms) []^{I} : T → {U⇀U} is a term interpretation function over interpretation I = ⟨U, V, A⟩ s.t.

• [:]^{I} is the identity function on U, and

• [τα]^{I} is the functional composition of [τ]^{I} and A(α). Definition 8 (Interpretation of Descriptions) [[]]^{I} : D → P ow(U) is a description interpretation function over interpretation I = ⟨U, V, A⟩ s.t. (τ, τ_{1}, τ_{2} ∈ T ; φ ∈ V; δ, δ_{1}, δ_{2} ∈ D):

• [[τ ∼ φ]]^{I} = {u ∈ U | [τ]^{I}(u) is defined and V([τ]^{I}(u)) = φ},

• [[τ_{1} ≈ τ_{2}]]^{I} = \{u ∈ U | \begin{matrix}[τ_{1}]^{I}(u) is defined, \\ [τ_{2}]^{I}(u) is defined, and \\ [τ_{1}]^{I}(u) = [τ_{2}]^{I}(u) \end{matrix} \},

• [[¬δ]]^{I} = U \ [[δ]]^{I}

• [[(δ_{1} ∧ δ_{2})]]^{I} = [[δ_{1}]]^{I} ∩ [[δ_{2}]]^{I}

• [[(δ_{1} ∨ δ_{2})]]^{I} = [[δ_{1}]]^{I} ∪ [[δ_{2}]]^{I}

• [[(δ_{1} → δ_{2})]]^{I} = (U \ [[δ_{1}]]^{I}) ∪ [[δ_{2}]]^{I} Definition 9 (Interpretation of a Theory) A theory is interpreted conjunctively. [[[]]]^{I} : P ow(D) → P ow(U) is a theory interpretation function over interpretation I = ⟨U, V, A⟩ s.t.

13We write {X⇀Y } for the set of partial functions from set X to set Y.

[[[Θ]]]^{I} = ⋂{[[δ]]^{I} | δ ∈ D}

Definition 10 (Satisfiability) A theory Θ is satisfiable iff there is an interpretation I s.t.

• [[[Θ]]]^{I} ≠ ∅

Definition 11 (Model) An interpretation I = ⟨U, V, A⟩ is a model of a theory Θ if [[[Θ]]]^{I} = U

The definitions above define a class of formal languages which can be used to express hpsg grammars. We only list these definitions here to make it possible to follow the formal definition and interpretation of the linguistic lexical rule notation in the next sections. A discussion of the formal language of King is beyond the scope of this paper. The reader interested in such a discussion is referred to King (1994).

5.2 The syntax of the linguistic lexical rule notation

Definition 12 (Lexical Rule Signature) Every signature S for which the following condition holds is a lexical rule signature S_{lr}.

• lex rule ∈ V and

• in, out ∈ A and

• approp(lex rule, in) = {word} and

• approp(lex rule, out) = {word}.

Definition 13 (L-Description) Let ♭ and ♯ be reserved symbols. With respect to a lexical rule signature S_{lr} let T be a set of terms, D a set of descriptions. A L-description is a member of the smallest set L s.t.

• d ∈ L  if d ∈ D  and

• :outμ ∼ ♭ ∈ L if μ ∈ A^{+} and

• :outμ♯ ∈ L if μ ∈ A^{+}.

Definition 14 (Linguistic Lexical Rule) With respect to a given lexical rule signature S_{lr} a linguistic lexical rule llr is a subset of the set of L-descriptions L containing at least the following literals (φ ∈ V; μ, μ_{1}, μ_{2} ∈ A^{+}):

• : ∼ lex rule and

• :outμ ∼ φ or :outμ_{1} ≈ :outμ_{2} or :outμ ∼ ♭ or :outμ♯.

There’s nothing complicated going on here. We just add the additional llr notation by defining l-descriptions with respect to a lexical rule signature. A linguistic lexical rule then consists of l-descriptions, and for convenience sake we ask for an llr-out containing at least one specification.

In most hpsg theories proposed in the literature, avms are used as descriptions instead of the term notation introduced above. avms can be seen as a kind of normal form representation for descriptions. We already introduced a notation for linguistic lexical rules in figure 9 on p. 8. Now that we’ve introduced the formal notation for linguistic lexical rules, let us illustrate the different ways in which one can write down llrs with an example (which is not intended to say much but just show the way things are written down). We will use the notation shown in figure 21 on the left as shorthand for the avm shown on the right, which in the formal notation defined above is expressed as shown below that.^{14}

[\begin{matrix}B & 1 \\ X & 1 \\ Y & & \left[{Z 1 \atop u}\right] \end{matrix}] ↦ [\begin{matrix}A & ♭ \\ B & ♯ \\ U|V & ♭ 2 \\ X & ♯ 2 \end{matrix} ]  [ \begin{matrix}& in & [\begin{matrix}B & 1 \\ X & 1 \\ Y & & \left[{Z 1 \atop u}\right] \end{matrix}] \\ & out & [\begin{matrix}A & ♭ \\ B & ♯ \\ U|V & ♭ 2 \\ X & ♯ 2 \end{matrix} ] \\ lex rule \end{matrix}]

: ∼ lex rule ∧ :in B ≈ :in X ∧ :in X ≈ :in Y Z ∧ :in Y ∼ u ∧

:out A ∼ ♭ ∧ :out B♯ ∧ :out U V ∼ ♭ ∧ :out U V ≈ :out X ∧ :out X♯

Figure 21: Three ways to write down llrs

5.3 A normal form for L-descriptions

In section 4.1 we saw that the l-descriptions making up the llr need to be normalized to have a consistent variety assigned to each defined attribute, which is needed for the mapping from llrs to lrs. This section serves to introduce a normal form for descriptions. It reports work carried out in Götz (1993) and Kepser (1994). Originally, the normalization algorithm is used to determine if a given description is satisfiable.

The linguist writes down llrs. So we want to normalize normalize l-descriptions, not simple descriptions. Since l-descriptions are a simple extension of descriptions with two additional statements for type and path equality elimination, we only need to add two trivial clauses to the description normalization algorithm of Götz (1993) to obtain an algorithm which transforms an l-description into normal form.

First, we need to introduce some additional terminology.

Definition 15 (Terms and subterms in Σ) The set Term(Σ) contains all paths occurring in a set of literals Σ and their subpaths (τ ∈ T ; π ∈ A^{∗}; φ ∈ V):

Term(Σ) =  {τ ∈ T | (¬) τπ ≈ τ′ ∈ Σ}
∪ {τ ∈ T | (¬) τ′ ≈ τπ ∈ Σ}
∪ {τ ∈ T | (¬) τπ ∼ φ ∈ Σ}

14Since the path equality relation is transitive, there are several possibilities to encode the example in the formal notation. Normalization (cf., section 5.3) introduces all path equalities which can be inferred due to transitivity.

Definition 16 (Clause and Matrix)

• A clause Σ is a finite (possibly empty) set of literals.

• A matrix Γ is a finite (possibly empty) set of clauses. Definition 17 (Interpretation of a Clause and a Matrix)

• A clause is interpreted conjunctively. If Σ is a clause, then [[Σ]]^{I} = ⋂_{δ∈Σ} [[δ]]^{I}.

• A matrix is interpreted disjunctively. If Γ is a matrix, then [[Γ]]^{I} = ⋃_{Σ∈Γ} [[Γ]]^{I}.

The conversion from l-descriptions to its normal form proceeds in two steps. First, the l-description is transformed into disjunctive normal form, i.e., where all negations are pulled in and the disjuncts are on the top level. The resulting matrix Γ is a finite set, each element of which represents one disjunct. Each disjunct is a clause which consists of a finite set of literals. Since the transformation into disjunctive normal form is a rather standard procedure, we simply assume its existence here. Second, the resulting matrix is normalized. We start with a declarative characterization of what it means for an l-description to be in normal form. Definition 18 (Normal Clause) A set Σ of literals is normal iff the following conditions hold (τ, τ_{1}, τ_{2} ∈ Term(Σ); φ, φ_{1}, φ_{2} ∈ V; α ∈ A; π ∈ A^{∗}) Original:

1. : ≈ : ∈ Σ (root is defined)

2. if τ_{1} ≈ τ_{2} ∈ Σ then τ_{2} ≈ τ_{1} ∈ Σ; (symmetry of ≈)

3. if τ_{1} ≈ τ_{2}, τ_{2} ≈ τ_{3} ∈ Σ then τ_{1} ≈ τ_{3} ∈ Σ; (transitivity)

4. if τπ ≈ τπ ∈ Σ then τ ≈ τ ∈ Σ; (prefix closure)

5. if τ_{1} ≈ τ_{2}, τ_{1}π ≈ τ_{1}π, τ_{2}π ≈ τ_{2}π ∈ Σ then τ_{1}π ≈ τ_{2}π ∈ Σ; (≈ and path extensions)

6. if τ ≈ τ ∈ Σ then for some φ ∈ V, τ ∼ φ ∈ Σ; (exhaustive typing)

7. if for some φ ∈ V, τ ∼ φ ∈ Σ then τ ≈ τ ∈ Σ; (∼ path is defined)

8. if τ_{1} ≈ τ_{2} ∈ Σ, τ_{1} ∼ φ_{1} ∈ Σ, τ_{2} ∼ φ_{2} ∈ Σ then φ_{1} = φ_{2}; (≈ and ∼)

9. if τ ∼ φ_{1} ∈ Σ, τα ∼ φ_{2} ∈ Σ then φ_{2} ∈ approp(φ_{1}, α); (appropriateness 1)

10. if τ ∼ φ ∈ Σ, τα ∈ Term(Σ), approp(φ, α) ≠ ∅ then τα ≈ τα ∈ Σ; (appropriateness 2)

11. if ¬δ ∈ Σ then δ ∉ Σ. (no contradictions) Additional:

12. if τ ∼ ♭ ∈ Σ then τ ≈ τ ∈ Σ; (∼ ♭ path is defined)

13. if τ♯ ∈ Σ then τ ≈ τ ∈ Σ; (♯ path is defined)

14. if :outπα ≈ :outπα,:inπ ∼ φ ∈ Σ, approp(φ, α) ≠ ∅ then :inπα ≈ :inπα ∈ Σ; (corresponding in-paths are defined)

The algorithm which takes an L-descriptions as a DNF matrix and returns its normal form is given below as a set of rewrite rules on sets of clauses. Γ is used as variable over sets of clauses and Σ as variable over clauses. Readers interested in the formal properties of the algorithm and a discussion of the normal form are referred to Kepser (1994, section II).

Algorithm 1 (Clause Normalization) The algorithm consists of a sequence rewrite rule applications. One step of the algorithm is the application of exactly one rewrite rule. The algorithm terminates, if no rule can be applied (any more). A rule applies to a set of clauses Γ′ only if the left hand side of the rule matches Γ′, and if the right hand side is a valid set description under the same variable assignment. The rewrite rules are (φ_{1}, φ_{2} ∈ V; α ∈ A; π ∈ A^{∗}) :

Γ ⊎ {Σ} ⟶ Γ ∪ {Σ ⊎ {:≈:}}  (1)
Γ ⊎ {Σ ⊎ {τ_{1} ≈ τ_{2}}} ⟶ Γ ∪ {Σ ⊎ {τ_{1} ≈ τ_{2}} ⊎ {τ_{2} ≈ τ_{1}}}  (2)
Γ ⊎ {Σ ⊎ {τ_{1} ≈ τ_{2}, τ_{2} ≈ τ_{3}}} ⟶ Γ ∪ {Σ ⊎ {τ_{1} ≈ τ_{2}, τ_{2} ≈ τ_{3}} ⊎ {τ_{1} ≈ τ_{3}}}  (3)
Γ ⊎ {Σ ⊎ {τσ ≈ τσ}} ⟶ Γ ∪ {Σ ⊎ {τσ ≈ τσ, τ ≈ τ}}  (4)
Γ ⊎ {Σ ⊎ {τ_{1} ≈ τ_{2}, τ_{1}σ ≈ τ_{1}σ, ⟶ Γ ∪ {Σ ⊎ {τ_{1} ≈ τ_{2}, τ_{1}σ ≈ τ_{1}σ,  (5)
τ_{2}σ ≈ τ_{2}σ}}  τ_{2}σ ≈ τ_{2}σ} ⊎ {τ_{1}σ ≈ τ_{2}σ}}
Γ ⊎ \{Σ ⊎ \{τ ≈ τ\}\} ⟶ \begin{matrix}Γ ∪ \{Σ ⊎ \{τ ≈ τ, τ ∼ φ\} | φ ∈ V\}, \\ if ∀φ′. τ ∼ φ′ ∉ Σ \end{matrix}  (6)
Γ ⊎ {Σ ⊎ {τ ∼ φ}} ⟶ Γ ∪ {Σ ⊎ {τ ∼ φ, τ ≈ τ}}  (7)
Γ ⊎ {Σ ⊎ {τ_{1} ≈ τ_{2}, τ_{1} ∼ φ_{1}, ⟶ Γ, if φ_{1} ≠ φ_{2}  (8)
τ_{2} ∼ φ_{2}}}
Γ ⊎ {Σ ⊎ {τ ∼ φ_{1}, τα ∼ φ_{2}}} ⟶ Γ, if φ_{2} ∉ approp(φ_{1}, α)  (9)

Γ ⊎ {Σ ⊎ {τ ∼ φ}} ⟶ Γ ∪ {Σ ⊎ {τ ∼ φ, τα ≈ τα}},

if τα ∈ Term(Σ) and approp(φ, α) ≠ ∅

(10)

Γ ⊎ {Σ ⊎ {δ, ¬δ}} ⟶ Γ, for any positive literal δ  (11)
Γ ⊎ {Σ ⊎ {τ ∼ ♭}} ⟶ Γ ∪ {Σ ⊎ {τ ∼ ♭, τ ≈ τ}}  (12)
Γ ⊎ {Σ ⊎ {τ♯}} ⟶ Γ ∪ {Σ ⊎ {τ♯, τ ≈ τ}}  (13)
Γ ⊎ \{Σ ⊎ \begin{cases}:outπα ≈ :outπα, \\ :inπ ∼ φ\}\} \end{cases} ⟶ Γ ∪ \{Σ ⊎ \begin{cases}:outπα ≈ :outπα, \\ :inπ ∼ φ, \\ :inπα ≈ :inπα\}\}, if approp(φ, α) ≠ ∅ \end{cases}(14)

Each rewrite rule corresponds to a line in the definition of a normal clause. Line 3 of definition 18, for example, demands transitivity of path equality. The corresponding rewrite rule (3) in algorithm 1 picks out a clause with two literals expressing path equalities and adds a literal expressing the path equality resulting from transitivity, if it is not already part of the clause. Note the use of ordinary (∪) and disjoint union (⊎). The last occurrence of disjoint union in the rewrite rule (3) ensures that this rule will only apply, if the literal to be added was not part of the original clause, i.e., if transitivity for the two literals did not already hold in Σ.

The original normalization algorithm of Götz (1993) consists of rules 1–11. Since we are dealing with L-descriptions, in addition we have to take care of the new symbols ♭, and ♯. For each such literal, rule (12) adds a literal defining the corresponding path. The rest of the algorithm will then ensure that each subpath is also defined and that each (sub)path is assigned the possible varieties. Finally, rule (13) ensures that for each path in the outdescription the corresponding path in the in-description is introduced, if it is appropriate.

6 A Semantics for the linguistic lexical rule notation

We define an algorithm which realizes a function from lexical rules as specified by the linguist (llr) to enriched descriptions of lexical rule objects which can be given the standard set theoretical interpretation defined in section 5.1.^{15} The conversion from llr to ordinary descriptions proceeds in two steps. First, the llr is converted into normal form, then the normal form llr is enriched with additional path equalities and variety assignments to encode the property transfer which is only implicit in the llr. As a result of enriching the llr we obtain an ordinary description, i.e., a lr, which is interpreted in the normal way.

6.1 Enriching a llr matrix: Intro

We saw in section 5.3 what it means for a l-description to be in normal form. Now we turn to the enriching algorithm. The input to the enriching algorithm is a llr in normal form. A normalized llr is a matrix Γ^{llr}, a finite set, each element of which represents one disjunct. Each disjunct is a clause which consists of a finite set of literals.

Take a normalized llr and apply the following steps:

1. For every clause Σ in the llr matrix, define a new matrix Γ = {Σ}.

2. With each such Γ obtain an enriched matrix Γ^{e} by applying a sequence of rewrite rules with respect to Σ until no rules can be applied.

The transfer enriched llr matrix Γ^{lr} is the union of all transfer enriched matrices Γ^{e} obtained, from which all inconsistent clauses and all literals of the form τ♯ and τ ∼ ♭ have been eliminated. (τ ∈ T )

6.2 An enriching algorithm

Algorithm 2 (Transfer enriching a llr matrix) A rule applies to a matrix Γ with respect to Σ iff the matrix matches the left hand side of the rule and the right hand side is a valid set description under the same variable assignment. (φ_{1}, φ_{2} ∈ V; α ∈ A; π ∈ A^{∗})

The rewrite rules are:

Γ′ ⊎ \{Σ′ ∪ \begin{cases}:inπ ∼ φ_{1}, \\ :outπ ∼ φ_{2} \end{cases}\}\}
⊎ \{Σ′′ ∪ \begin{cases}:inπ ∼ φ_{1}, \\ :outπ ∼ φ_{1} \end{cases}\}\}

⟶_{Σ} Γ′ ∪ \{Σ′′ ∪ \begin{cases}:inπ ∼ φ_{1}, \\ :outπ ∼ φ_{1} \end{cases}\}\} (1)

if φ_{1} ≠ φ_{2} and :outπ ∼ ♭ ∉ Σ

Γ′ ⊎ \{Σ′ ⊎ \begin{cases}:outπ ∼ φ_{1}, \\ :inπ ∼ φ_{2} \end{cases}\}\}  ⟶_{Σ} Γ′ ∪  (2)

\{Σ′ ⊎ \begin{cases}:outπ ∼ φ_{1}, \\ :inπ ∼ φ_{2}, \\ :inπα ≈ :outπα \end{cases} | \begin{matrix}approp(φ_{1}, α)∩ \\ approp(φ_{2}, α) ≠ ∅ \end{matrix}\}\}

if :outπα ≈ :outπα ∉ Σ

15The formal setup used in this section is modeled after the description normalization algorithm of Götz (1993) which is reported in Kepser (1994).

The above rewrite rules are a formal version of the design decisions 1 and 2. In prose, the rewrite rules do the following:

1. Check if the type on a certain in-path is compatible with that on the corresponding out-path. I.e., check if certain varieties are assigned to both the in and the out-path. If that’s the case, eliminate the disjunct in which the in-path and the out-path are not assigned the same variety.

2. Introduce structure sharing between llr-in and llr-out for all attributes α extending a path which is defined in llr-out in case α is appropriate for both the path in llr-in and the corresponding one in llr-out and the path extended by α is not itself defined in llr-out. Note that the last conjunct includes the case that the path extended by α is specified with a path or type elimination marker.

6.3 An example

Now that we’re done exploring and formalizing the llr-n, let us end this paper with a linguistic example taken from Pollard and Sag (1994, chapter 9, p. 378), the Complement Extraction Lexical Rule (celr). There are two reasons for looking at this example. On the one hand the signature is explicitly given by Pollard and Sag. This is necessary to understand what goes on with a linguistic lexical rule. On the other hand, the celr is rather difficult to express without a formalized lexical rule mechanism and can cause unwanted results under some interpretations as discussed by Höhle (1995). So this makes it a good test case to see whether we’ve made things any clearer, even though a lot of the possibilities which we envisaged in the design of the llr-n will naturally play no role in this particular case.

Since the different ways to encode relations in hpsg are a separate issue and we don’t want to complicate the example with a junk slot encoding of append and union, we use a simplified version of the celr. The particular instance of the celr we discuss treats the second element on COMPS and SUBCAT for entries with an empty SLASH set instead of treating any element on COMPS and any on SUBCAT with any SLASH set. The rest of the rule we use is like in the original celr. Figure 22 shows how in our setup the celr can be specified by the linguist. Note that only those parts which are intended to be changed need to be mentioned at all. No type or path equality elimination is needed for this example.

[\begin{matrix}SYNSEM & [\begin{matrix}LOC|CAT|VAL|COMPS|R & ⟨ 3 [LOC 1 ] | 5 ⟩ \\ NLOC|INHER|SLASH & \{\} \end{matrix}] \\ SUBCAT|R|F & 3 \end{matrix}] ↦

SYNSEM [\begin{matrix}LOC|CAT|VAL|COMPS|R & 5 \\ NLOC|INHER|SLASH & \{ 1 \} \end{matrix}]
SUBCAT|R|F|NLOC|INHER|SLASH { 1 }

Figure 22: The Complement Extraction Lexical Rule (simplified)^{16}

Since no typing information is specified in llr-out and those attributes which have types as values that have subtypes (HEAD, NUCLEUS, RESTIND, DTRS, …) are not mentioned in llr-out, all the work to map the celr into a description is done by the rewrite rule that adds path equalities between the in- and the out-description. The lr resulting from enriching the celr is shown in figure 23.

16Where tags are needed, the same tag numbers as in the original formulation of Pollard and Sag are used.

F and R are used as abbreviated notation for the ne list attributes FIRST and REST.

lex rule

\underline{IN}  [\begin{matrix}word \\ PHON & @1 \\ \underline{SYNSEM} & [\begin{matrix}synsem \\ \underline{LOC} & [\begin{matrix}loc \\ \underline{CAT} & [\begin{matrix}cat \\ HEAD & @2 \\ \underline{VAL} & [\begin{matrix}val \\ \underline{COMPS} & [\begin{matrix}ne list \\ F & @3 \\ \underline{R} & [\begin{matrix}ne list \\ \underline{F} & 3 \left[{synsem \atop \underline{LOC}  1}\right] \\ \underline{R} & 5 \end{matrix}] \end{matrix}] \\ SUBJ & @4 \\ SPR & @5 \end{matrix}] \\ MARK & @6 \end{matrix}] \\ CONT & @7 \\ CONX & @8 \end{matrix}] \\ \underline{NLOC} & [\underline{INHER} [\begin{matrix}nloc1 \\ \underline{SLASH} & \{\} \\ REL & @9 \\ QUE & @10 \end{matrix} ]_{TO-B @11}] \end{matrix}] \\ \underline{SUBCAT} & [\begin{matrix}ne list \\ F & @12 \\ \underline{R} & [\underline{F} 3 [\begin{matrix}LOC & @13 \\ NLOC & [\begin{matrix}INHER & [\begin{matrix}REL & @14 \\ QUE & @15 \end{matrix} ] \\ TO-B & @16 \end{matrix}] \end{matrix}]_{R @17}^{ne list}] \end{matrix}] \\ QSTORE & @18 \\ RETR & @19 \end{matrix}]

\underline{OUT}  [\begin{matrix}word \\ PHON & @1 \\ \underline{SYNSEM} & [\begin{matrix}synsem \\ \underline{LOC} & [\begin{matrix}loc \\ \underline{CAT} & [\begin{matrix}cat \\ HEAD & @2 \\ \underline{VAL} & [\begin{matrix}val \\ \underline{COMPS} & [\begin{matrix}ne list \\ F & @3 \\ \underline{R} & 5 \end{matrix} ] \\ SUBJ & @4 \\ SPR & @5 \end{matrix}] \\ MARK & @6 \end{matrix}] \\ CONT & @7 \\ CONX & @8 \end{matrix}] \\ \underline{NLOC} & [\underline{INHER} [\begin{matrix}nloc1 \\ \underline{SLASH} & \{ 1 \} \\ REL & @9 \\ QUE & @10 \end{matrix} ]_{TO-B @11}^{nloc}] \end{matrix}] \\ \underline{SUBCAT} & [\begin{matrix}ne list \\ F & @12 \\ \underline{R} & [\underline{F} [\begin{matrix}synsem \\ LOC & @13 \\ \underline{NLOC} & [\begin{matrix}nloc \\ \underline{INHER} & [\begin{matrix}\underline{SLASH} & \{ 1 \} \\ REL & @14 \\ QUE & @15 \end{matrix} ] \\ TO-B & @16 \end{matrix}] \end{matrix}]_{R @17}^{ne list}] \end{matrix}] \\ QSTORE & @18 \\ RETR & @19 \end{matrix}]

Figure 23: The explicit lr resulting from enriching the celr of figure 22

To make it easier to read, the path equalities which were added by the enriching algorithm bear an @ sign before the number in order to distinguish them from the tags present in the linguistic lexical rule. Also, the attributes that were part of the original linguistic specification are underlined. For each of these defined paths normalization introduced a specification :τ ≈ :τ to mark which paths are defined and variety specifications :τ ∼ φ. So, the varieties along the underlined paths in figure 23 are introduced by normalization. The path equalities marked with an @ are introduced by enriching: Along the defined paths the appropriate attributes are introduced and path equalities between paths in the in-specification and the out-specification are added for those attributes which directly extend a defined path but are not themselves defined, i.e., underlined.

Note that the element on the SUBCAT list of the output which corresponds to the one that is extracted from the COMPS list turns out to be identical to the element on the input’s SUBCAT list except for the NLOC|INHER|SLASH specification. This is just what was intended but what in the absence of a formalized lexical rule mechanism was not not formally expressed in the original formulation of the celr as discussed in footnote 37 on p. 378 of (Pollard and Sag, 1994)).

Regarding the problem of Höhle (1995), we had already mentioned in section 4.1.3 that this problem is caused by having to modify certain path equalities before ‘copying them over’ from the in-specification to the out-specification. Since we do no such copying, but rather specify path equalities between the in- and the out-specification this problem does not arise in our approach.

Finally, to take a place in the theory, the description in figure 23 is included as one of the disjuncts on the right-hand side of the type definition of type lex rule which we saw in figure 4 on p. 5.

7 Concluding Remarks

In this paper, we’ve tried to shed some light on a possibility to formalize lexical rules using a standard logical basis of hpsg. First, we defined lexical rules so that they can be constrained by ordinary descriptions. Then we explored and defined a linguistic lexical rule notation which allowed us to leave certain things implicit. Finally, we showed how we can get from the linguistic notation to the explicit constraints.

We believe there are some nice properties of such an approach: First of all, apart from the mapping from the linguistic notation to explicit constraints, we did not add any additional machinery to the logic. The semantics of the linguistic lexical rules after the mapping is provided by the standard King logic which is used for all of hpsg. The advantage this has for the linguist is that when it comes down to seeing exactly what a certain linguistic lexical rule means, (s)he can always take a look at the resulting enriched, fully explicit descriptions of lexical rules in the language used to write the rest of the hpsg theory, instead of having to interpret the linguistic lexical rules directly in some kind of additional formal system.

Second, the mapping from linguistic lexical rules to explicit constraints is done independent of the lexical entries. It suffices to look at the linguistic lexical rules and the signature to determine what remained implicit in the linguistic lexical rule notation and how it can be made explicit. This is possible because hpsg is built on a type feature logic and a closed word interpretation of a type hierarchy.

Third, the approach presented is highly modular and adaptable to the linguist’s needs: One can decide on the data structure for lexical rules one likes best (relations or ordinary descriptions), alter/extend the linguistic lexical rule notation in a way one likes, and alter/extend the rewrite rules which enrich linguistic lexical rules to ordinary descriptions in a way one likes. This is important until a real discussion of possibilities and linguistic consequences of various setups has shown what hpsg linguist’s really want to write down and what it’s supposed to mean.

And fourth, if one takes descriptions of lexical rule objects as basic encoding as we have done in the main part of the paper (and not ’proper’ relations as part of the relational extension as considered in the beginning), this makes it possible to hierarchically group lexical rules and express constraints on (groups of) lexical rules. This allows us to express general principles every lexical rule has to obey, and it makes it possible to express that a group of lexical rules shares certain properties.

Finally, as mentioned in the introduction, this paper builds on ideas developed in Meurers and Minnen (1995) and can be seen as providing a formal foundation for that computational proposal. The computational treatment proposed in Meurers and Minnen (1995) can be used for lexical rules producing an infinite lexicon since it avoids expanding out the lexicon under lexical rule application. The compiler at the heart of the computational treatment transforms a set of lexical rules into a set of relational constraints on lexical entries by considering the possible interaction of the set of lexical rules and the lexicon in an abstract way. The encoding is then advanced by program transformation techniques to allow on the fly application of the relations encoding the lexical rules.

References

Aït-Kaci, Hassan. 1984. A lattice theoretic approach to computation based on a calculus of partially ordered type structures. Ph.D. thesis, University of Pennsylvania.

Calcagno, Mike. 1995. Interpreting lexical rules. In Proceedings of the Conference on Formal Grammar, Barcelona. Also in: Proceedings of the ACQUILEX II Workshop on Lexical Rules, 1995, Cambridge, UK.

Calcagno, Mike and Carl Pollard. 1995. Lexical rules in HPSG: What are they? In preparation for the Acquilex II Workshop on Lexical Rules.

Carpenter, Bob. 1992. The Logic of Typed Feature Structures - With Applications to Unification Grammars, Logic Programs and Constraint Resolution, volume 32 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, New York.

Copestake, Ann. 1992. The Representation of Lexical Semantic Information. Cognitive science research paper CSRP 280, University of Sussex.

Dörre, Jochen. 1994. Feature-Logik und Semiunifikation. Arbeitspapiere des SFB 340 Nr. 48, Universität Stuttgart.

Götz, Thilo. 1993. A normal form algorithm for king’s descriptive formalisms. unpublished term paper, Universität Tübingen.

Götz, Thilo. 1995. Compiling HPSG constraint grammars into logic programs. Draft, extended version of a paper presented at CLNLP 95, Edinburgh, Scotland.

Hinrichs, Erhard and Tsuneko Nakazawa. 1994. Partial-VP and Split-NP topicalization in German: An HPSG analysis. In (Hinrichs, Meurers, and Nakazawa, 1994).

Hinrichs, Erhard W., W. Detmar Meurers, and Tsuneko Nakazawa. 1994. Partial-VP and Split-NP topicalization in German – An HPSG analysis and its implementation. Arbeitspapiere des SFB 340 Nr. 58, Universität Tübingen.

Höhfeld, M. and Gert Smolka. 1988. Definite relations over constraint languages. LILOG technical report, number 53, IBM Deutschland GmbH.

Höhle, Tilman N. 1995. The complement extraction lexical rule and variable argument raising. Handout for a talk given at the HPSG Workshop held in Tübingen on 21–23. June 1995.

Keller, Frank. 1993. Encoding HPSG grammars in TFS, part III - encoding revised HPSG. ms., Universität Stuttgart.

Kepser, Stephan. 1994. A satisfiability algorithm for a logic for typed feature structures. Master’s thesis, Universität Tübingen.

King, Paul. 1989. A Logical Formalism for Head-Driven Phrase Structure Grammar. Ph.D. thesis, University of Manchester.

King, Paul. 1994. An expanded logical formalism for Head-Driven Phrase Structure Grammar. Arbeitspapiere des SFB 340 59, University of Tübingen.

Kuhn, Jonas. 1993. Encoding HPSG grammars in TFS, Part I & II - Tutorial. ms., Universität Stuttgart.

Meurers, W. Detmar. 1993. A TFS implementation of C. Pollard: “On Head Non-Movement”. Implementation. SFB 340/B4, Universität Tübingen.

Meurers, W. Detmar. 1994. On implementing an HPSG theory – Aspects of the logical architecture, the formalization, and the implementation of head-driven phrase structure grammars. In: Erhard W. Hinrichs, W. Detmar Meurers, and Tsuneko Nakazawa: Partial-VP and Split-NP Topicalization in German – An HPSG Analysis and its Implementation. Arbeitspapiere des SFB 340 Nr. 58, Universität Tübingen.

Meurers, W. Detmar and Guido Minnen. 1995. A computational treatment of HPSG lexical rules as covariation in lexical entries. In Proceedings of the Fifth International Workshop on Natural Language Understanding and Logic Programming, Lisbon, Portugal.

Pollard, Carl. 1993. Lexical rules and metadescriptions. Handout, October 5, 1993, Universität Stuttgart.

Pollard, Carl and Ivan A. Sag. 1987. Information-based Syntax and Semantics, Vol. 1. Number 13 in Lecture Notes. CSLI Publications, Stanford University. Distributed by University of Chicago Press.

Pollard, Carl and Ivan A. Sag. 1994. Head-Driven Phrase Structure Grammar. University of Chicago Press, Chicago.