Generic rules and non-constituent coordination

GENERIC RULES AND NON-CONSTITUENT COORDINATION Julio Gonzalo UNED julio©ieec .uned.es Teresa Solfas Universidad de Valladolid solias©cpd.uva.es Abstract We present a metagrammatical formalism, generic rules, to give a default interpretation to grammar rules. Our formalism introduces a process of dynamic binding interfacing the level of pure grammatical knowledge representation and the parsing level. We present an approach to non-constituent coordination within categorial grammars, and reformulate it as a generic rule. This reformulation is context-free parsable and reduces drastically the search space associated to the parsing task for such phenomena. 1 Introduction Grammatical theories always make a distinction between unmarked and marked phenomena. The general case is to use certain mechanisms which are likely to deal with regular behaviour. More complex mechanisms should be available when exceptional behaviour is present. However, this difference is not formally expressed in most grammar accounts of complex phenomena. The need to restrict licensing of additional grammar resources is commonly asserted outside of the formal framework used. As exceptional rules involve a higher computational cost, parsing processes associated to such formalisms become computationally intractable. Non-constituent coordination treatments show this pattern. In general, a conjunction com bines constituents. But .there are cases where the conjunction coordinates linguistic elements which do not form a constituent. For instance, consider' John went to Alabama in summer and to Spain in fall', The conjunction 'and' is coordinating ' to Alabama in summer' with ' to Spain in /arr, which do not form constituents. The solutions displayed in the literature incorporate additional grammatical resources to deal with such data. We would expect a high restriction on the use of the rules associated to this phenomena, but all we have is informal comments about when to apply them. That makes parsing time of the grammar exponential in the length of the string. Though there is a general concern on the need to make explicit some process of rule licensing, no formal framework has been proposed, to our knowledge, to regulate the interaction between regular and exceptional grammatical resources. In this paper we propose a metagrammatical formalism, generic rules, to give a different degree of specificity to each grammatical rule. We present an approach to parse non-constituent coordination within categorial grammars that can be parsed in polynomial time when reformulated as a generic rule. The essential idea is to introduce a process of dynamic binding interfacing the level of pure grammatical representation and the parsing processes. When the parsing process calls the grammar to combine linguistic objects, the dynamic binding process inspects the applicable grammatical resources, considers their different priority and returns an effective rule, or set of 99 rules, to be applied on such linguistic objects. This approach is inspired in the object-oriented programming paradigm, where polymorphism is exploited in order to get default and specific behaviour. In order to make dynamic binding a meaningful process, we will view generic and specific behaviour as object-oriented functions that map daughters information into mother features. A set of such functions will be called a generic rule. Precedence between them will be established according to the specificity of the type constraints on the daughters. This paper is structured as follows: first, we outline the main ideas behind our approach. Next, we make a more formal presentation of generic rules. Then, we turn to the linguistic problem of non-constituent coordination, and give a linguistic explanation within categorial grammar that uses the tuple operation in_troduced in [Solias, 1993, Morrill and Solias, 1993). Recognition with that grammar is NP-hard, as it is with most extensions of Lambek Calculus. We present, then, a reformulation of that grammar as a generic rule. The representational facilities of generic rules allow the specification of each grammatical resource at an appropriate level of specificity, drastically constraining the search space for the parsing task. 2 Generic Rules 2.1 Underlying Ideas Consider a context-free grammar -possibly augmented with functional restrictions attached to each rule -that includes the hierarchy VP➔ VP1 I VP2 I VP3 I VP4 I VPi and the rule S ➔ NP VP. If we decide to write down a new rule that specifies a different, more specific behaviour for VPi when combining with a NP, we could think of adding a new rule as: Si ➔ NP VPi. If our aim is to state this rule as the rule to be used when the VP belongs to the more specific subclass VPi, we want the production S ⇒ NP VPi to be valid, but not the production S ⇒ NP VP⇒ NP VPi. Just adding Si ➔ NP VPi to the _CFG does not capture the exceptional sense of the rule; in a CFG, both derivations are equally possible. We have two options to get the desired behaviour from the CFG. The first one is to keep S ➔ NP VP and rewrite the specific r1:1le Si ➔ NP VPi into the following set of rules: S -+ NP VP1 I NP VP2 I NP VP3 I NP VP4 (1) The second one is to rewrite the hierarchy, in order to keep the number of rules invariant: VP➔ VPi I VPt VPt -+ VP1 I VP2 I VP3 I VP4 S ➔ NP VPt Si➔ NP VPi (2) None of these options is an incremental way of capturing exceptions in a grammar. The in troduction of'an exception forces the revision of previously described lexical types and grammar rules. This naive-example exemplifies a problem that becomes significant when an operation or rule carries on most of the information-combining task. This is a standard situation in lexicalist approaches to grammar. For instance, [Dowty, 1988) proposes a distinction between a basic categorial grammar, which only includes forward and backward application, and an extended grammar that also includes type raising and functional composition. The basic grammar is used for most of the analysis, whereas the extended one should only be used in specific· situations such as non-constituent coordination� It is suggested that this rules should be licensed only when functional application fails to parse a string. However, no formalization of the different status of such rules is offered. We propose a formalism to express and handle default and exceptional rules within a phrase structure approach that permits this kind of representations. Our formalism describes rules as object-oriented functions that map daughters information into mother features. As in object oriented programming, precedence between rules is not given statically iri the linguistic signa ture, but it is dynamically established upon the types of the input structures of the composi tional process. When combining two constituents, a metagrammatical mechanism establishes 100 a partial order for the candidate rules and selects the IDibst appropriate rule ( or set of rules) to be applied. I Before defining such framework, let us introduce the proposal with a generic rule repre󰉃 sentation for the naive example above. The generic, rule having the desired behaviour for rule S ➔ NP VP and rule Si➔ NP VPi has this aspect: SYN -{ SYNNP®VP(x, y) = S -SYNNP®VPi (x, y) = Si (3) Equation 3 describes a generic rule, SYN, that returns a type for the composition of two linguistic objects. SYN NP®VP ( x, y) = S is a partial rule applicable when the arguments :z:, y belong to the types NP, VP, in that order. SYN NP®VP i ( x, y) = Si is applicable when the arguments belong to the types NP, VP i. A bottom-up parsing process may call SYN when it tries to combine two objects with types x, y. The applicable partial rules will be {SYN a®b I a ::; x, b ::; y }. The natural way to establish precedence between rules is attending to the specificity of the type constraints of their arguments: SYN a®b will be more specific than SYN c®d if a ::; c, b ::; d. Some examples of the application of SYN would be: SYN(NP, VP)= S SYN( VP2, NP) =1- SYN(NP, VP2) = S SYN(NP, VPi) = Si In each case, the following partial rules have been applied: SYN(NP, VP)=} SYNNP®VP SYN ( VP 2, NP) -<===> 1-( no applicable rule) SYN (NP, VP 2) -<===> SYN NP® VP SYN(NP, VPi)-<===> SYNNP®VP (4) (5) In that way, we have the ability to express default rules, and rules with different degrees of specificity in an incremental way, without a need to give them different formal status. Also, only minor changes have to be made to a CFG parsing algorithm in order to work with generic rules. 2.2 Definition of a Generic Rule Consider a partially ordered set (poset) (::;, T) ·and a domain of linguistic objects O typed with (�, T) (i.e., there is a function type:O ➔ T). Consider also an informational domain � associated to O by means of a function <f>:O ➔ � (perhaps multivaluated) that associates at least one element in � to every object of 0. A generic rule Gover the tuple ((::;, T),O,�) is another tuple ((j, T*),F,Q), where: • F is a set of functions, that will be called partial rules, of the form: where t 1, t 2 E T, and the following condition holds on the set of partial rules: Vft1®t2 ,fq1®q2 E F, t1 = ql A t2 = q2-<===> ft1®t2 = fq1®q2. • (j, T*) is a partially ordered poset defined over Fas follows: T* = { t 1®t 2 1ft i®t 2 E F} V:z:1®:z:2 , y10y2 ET* x1®:z:2 j y10y2 -<===> x1::; y1 and :z:2::; y2 We call cartesian poset (j, T*) over a poset (::;, T) to any subset of T x T equipped with the partial ordering relation j. We call cartesian type of a partial rule ft 1 ®t 2 • to the type specification t 1 ®t 2 . 101 sign --------------- pronoun noun I I possessive count-noun (=s, T*U{ her®earrings}) sign®sign I pronoun®s i gn possessive®noun pronoun®count-noun l f ;;®;a-r;ic=n;s: --------/ Figure 1: vVhen the generic rule associated to T* is invoked to compose her and earrings, a cartesian type her®earrings is dynamically considered, but it has more than one direct supertype; therefore, there is not a single most specific rule to be applied on that constituents. • Vx1,x2 E T,9(x1,x2) = ft1@t2 such that t1®t2 is the lowest upper bound of x 1 ®x 2 in T* U { x 1 ®x 2 } . 9 is called the dynamic binding function for G. It interfaces parsing processes with the grammar, selecting the most specific partial rule in F given two arguments of types x 1, x2• Note that T* is a subset of the cartesian product T x T, and that the partial ordering relation =s is deduced from the relation � that holds between the elements of T. By means of the definition of cartesian poset, we have managed to axiomatize precedence issues between partial rules: turning the dynamic binding process into a simple order checking over the elements of a poset. The function 9 provides the interface of the generic rule, as a system of object-oriented functions, with the parsing process that calls it. In particular, the dynamic binding function provides the default interpretation for partial rules. Given a pair of arguments of types x 1, x 2, a dynamic extension T* U { :z: 1®x2 } of the original cartesian poset (=s, T*) that includes the cartesian type x 10:z: 2 is considered. In virtue of the definition of the partial ordering relation =s, the new type x1©:z:2 takes its place in the hierarchy. Its supertypes denote all the applicable rules to compose the pair of arguments, and the partial ordering between this supertypes denotes precedence between them. The action of the generic rule G over a couple of linguistic objects with types x1, x2 and associated expressions cp1, cp2 is given by Q(:z:1, x2)(cp1, cp2). In our definition, precedence is used to keep the most specific rule and override the rest. Hmvever, more sophisticated binding processes could be considered. For instance, if the partial rules were unification constraints, some default version of unification could be performed on the applicable rules, taking their relative precedence into account. We have adopted the restriction of binary branching (binary rules) to take full advantage of the concept of dynamic binding with the minimum effort. However, this is not a serious limitation: most linguistically significant rules are binary, and those which are not can be easily converted in binary rules. 2.3 Well-formedness Given the definition of the preceding section, there can be situations where precedence conflicts cannot be solved. \Vhen the cartesian type that represents the arguments of a call to the generic rule has more than one direct supertype, there is not a single "most specific rule" (see the example in Figure 1). If this indeterminacy is possible for a given generic rule, we say that the Cartesian Poset (=s, T*) is not well-formed: A Cartesian Poset (=s, T*) is well-formed iff V x1®X:2 , y1®y2 E (j, T*) not ordered, such that m1 = x1 /\ y1 E (�, T) and "'2 = :z:.i I\ y2 E (�, T), it holds that m1®""2 E (j, T*) 1 1This definition assumes that the original poset is bounded complete, i.e., each pair of types have at most 102 This kind of indeterminacy appears also when dealing with multiple default inheritance [Daelemans et al., 1992] or default unification over feature structures with structure-sharing [Bouma, 1992, Carpenter, 1993], and can only be solved adding extra ordering information or forbidding such situations. Our well-formedness condition adopts the first solution. The main reason is that the cartesian hierarchies are not defined by the user, but arranged by the system. Such conflicts are potentially dangerous, as the grammar writer is not necessarily aware of them. An advantage of the definition of well-formedness is that it can detect inconsistencies at compile-time and signal them for correction. 2.4 Parsing with Generic Rules A generic rule may interact with a phrase-structure grammar to perform the composition of some informational field. In [Gonzalo, 1995), for instance, we propose generic rules as a well󰉅 suited mechanism to perform categorial semantic interpretation as a modular process that interacts with a phrase-structure grammar. On the other hand, a grammar could be made up exclusively of generic rules, adequately combined to perform parsing. We will present a simple account of each of these possibilities. We will adopt here the deductive parsing approach described in [Shieber et al., 1994]; it provides a neat account of parsing systems, simplifying our presentation. We will start from a bottom-up shift reduce algorithm as presented in [Shieber et al., 1994]. We will gradually adopt this algorithm to capture generic rule parsing. Let a be a string of terminals Wi-Let [a• , j] stand for O'.Wj+i · · · Wn ⇒ W1 · · · Wn-In [Shieber et al., 1994] a shift-reduce bottom-up deductive parsing system is expressed as the following calculus: Axiom: [ • , O] Goal: [S •, n] Inference Rules: Shift Reduce [a• ,j] [awi+l • ,j + 1] [a,• ,j] B [aB • ,j] ➔' This parser can be augmented to do semantic interpretation. If each rule has an associated function that related the meanings of the elements in the rhs with the meaning of the lhs element, the basic tuples are [a•, j, </)]. The reduce rule carries on semantic composition:2 Reduce [ a, • ' j' <P < <P1 ... <Pb I >] [aB • ,j, <P < f(<P1 · · · <P1,1) >] B➔,, f where f is the semantic composition function associated to the rule B ➔,. We can augment the shift-reduce parser in a similar way to represent the interaction between a generic rule and a phrase-structure grammar. We have to take account of two differences between generic rule parsing and the syntactic-semantic parser above: 1. The action of the generic rule has to be specified through the dynamic binding function. There is not a partial rule associated to each context-free rule. 2. The interpretation of the context-free rules has to be slightly modified to take into account the hierarchization of non-terminals. A hierarchy is equivalent, in context-free terms, to a set of unary rules in which every inmediate-ordering relation is expressed writing a type as a left-hand side of a rule, and its subtype as the right-hand side. Being these rules "compiled" into the hierarchy, a context-free rule as T ➔ T1T2, has to be interpreted as T ➔ X1X2 such that X1 :'.S Ti, X2 :'.S T2. one common subtype. 2The other rules are modified trivially. 103 The basic element in the logic that represents the parsing algorithm is the same as in the preceding case: [ a • , j, 4>]. Now, 4> is an expression that belongs to the informational domain associated to a generic rule G. The reduce rule that takes account of the interaction of a generic rule with a context-free grammar is Reduce [ Q X l X 2 • , j, 4> < </J1 </J2 >] A➔ BC, X1 � B, X2 � C 9(x1,x2)(</>1,</>2) /..l (6) The interaction with the generic rule is expressed in the term 9 ( x 1, x 2) ( </>1 , </>2). The left part, 9 ( x 1, x 2), performs dynamic binding, returning the effective rule that will be applied on X1, X2. The side conditions on this rule are: one, that exists an applicable syntactic rule A ➔ BC, X l � B, X 2 � C. And two, that the generic function, applied over </>1, </>2, returns a positive result. Note that it could be the case that there is an appropriate syntactic rule, but the additional restrictions imposed by the generic rule do not hold 3• It is interesting to remark that the dynamic binding process depends on the particular objects in the Reduce rule, not only on the conditions of the context-free rule. That makes impossible to pre-attach an "effective partial rule" to each context-free rule at compilation time, such that the binding process could be performed off-line. This fact is reflected in the term 9(x1, x2). If it \Vere 9(B, C), binding could be done at compile time. Though this behaviour introduces and additional complexity factor in generic rule parsing, it allows the specification of semantic and syntactic processes as independent mechanisms that interact modularly. A particular case of generic rule is that in which the combination functions simply return a type, as in our first example. In such a rule, the role of every partial rule is similar to that of a context-free rule, and the generic rule works as a context-free grammar in which rules has a default interpretation. For this kind of generic rules, that combine syntactic information, it is senseless to consider their interaction with a context-free grammar, as they are _parsable by themselves. Such parsing does not differ substantially from context-free parsing. The main restriction is that, due to the functional interpretation of partial rules, bottom-up algorithms are best suited that top-down mechanisms, that would require the definition of inverse functiqns. The reduce rule that takes account of syntactic parsing with a generic rule can be described as follows: Reduce [ax1x2•,j] [aSYN(x1, x2)(x1, x2) • ,j] (7) The expression SY JV ( x 1, x 2) ( x 1, x 2), with both arguments repeated, may seem confusing. Note, however, that each couple of arguments plays very different roles. The first couple are the arguments of the dynamic binding function, from which an effective partial rnle is obtained. Such partial rule is then applied to the· second set of arguments. They are related to the informational domain associated to the generic rule, which is, in this case, the type information associated to the linguistic objects. The side condition, in this case, is precisely the one that licenses the syntactic combining operation. If SYN(x1, x2)(:z:1, x2) does not return a positive result, then we cannot build a phrase out of the arguments x 1, :z:2. The computational cost of parsing processes associated to this kind of generic rules carrying on syntactic information is obviously the same as the cost of parsing a context-free grammar. The only difference between both processes is the way to select the appropriate rule when the Reduce step is called. In context-free parsing, this step involves looking up the available rules and matching the objects involved with the right-hand side of the rules. In the worst case, this process introduces a factor G in the overall complexity of parsing, being G the size· of the 3This wot_1ld be the case of semantic disambiguation. 104 grammar. For a generic rule, the reduce rule involves introducing a new type in the hierarchy of rules. Again, this implies a factor Gin the overall complexity, being G the number of partial rules associated to the generic rule. The dependence with the length of the string is obviously the same, as the surface behaviour of a context-free grammar and a generic rule is exactly the same for bottom-up parsing. Another interesting case is when we have a generic rule to specify syntactic restrictions, and another one to perform semantic interpretation. It is easy to specify an algorithm to parse such grammars from the preceding cases. Now the elements of the logic have the form [a• ,j, <I>], and the parser includes the following reduce rule: Reduce [a:z:1:z:2 • ,j, <I>4>1<P2] SYN(:z:1, :z:2)(:z:1, :z:2) t..1 (8) [aSYN(:z: 1, :z:2)(:z: 1, :z:2) •, j, S£M(:z: 1, :z:2)(4>1, 4>2)] S£M(:z: 1, :z:2)(4>1, </>2) i..l Let us see a (linguistically weird) example. Consider the grammar made up of the following generic rules: SYN -{ SYNNP®VP(X, Y) = S (9) -SYNNP®VPi (X, Y) = Si SEM _ { SEMNP®VP(X, Y) = sem(X)(sem(Y)) (lO) - SEMproper-Notm®VP (X, Y) = sem(Y)(sem(X)) I\ (.\P.P(Pete))(sem(Y)) The syntactic rule has already been considered in section 2.1. We assume the same hierarchy of that example, augmented with a new type proper-noun :::; NP. The semantic generic rule takes account of a very special semantic issue, namely that Pete has a weak personality and imitates his friends in everything they do. If we consider the phrases • Betty : .\P.P(Betty) ; Betty s; proper-noun • got+angry : .\x.ANGRY(x) ; got+angry :::; VPi the application of the deductive system above to the string 'Betty got angry' would be as follows: 1. [•,O,] 2. [Betty•, 1, .\P.P(Betty)] (Shift) 3. [Betty got+angry •, 2, .XP.P(Betty), .\x.ANGRY(x)] (Shift) 4. [Si•, 2, ANGRY(Betty) /\ ANGRY(Pete)] (Reduce) In the only application of the reduce rule, the following terms were used: SYN(Betty,got+angry)(Betty,got+angry) = SYNNP0VPi (Betty,got+angry) = Si S£M(Betty, got+angry )(,\P.P(Betty, ,\x.ANGRY(x)) = SEMProper-Noun0VP (AP.P(Betty, Ax.ANGRY(x)) = ANGRY(Betty) A ANGRY(Pete) This example illustrates the point, stated before, that it is not possible to attach a semantic rule to each syntactic rule at compile time. It is, essentially, a dynamic binding process. A phrase-structure grammar with a one-to-one correspondence between syntactic and se mantic rules would need 12 pairs of rules to get the same behaviour as the two generic rules above. The incrementality and modularity of the generic rule approach is evident in this case. 105 3 Non-Constituent Coordination and Categorial Grammar The general scheme for coordination corresponds to the conjunction of constituents belonging to the same type: 'Nothing is certain, except death and taxes', ' Take the money and run', 'the long and winding road:. Within the categorial grammar framework, such cases are solved using the basic function application rules ( corresponding to the non-associative Lambek calculus in a sequent calculus presentation). Nevertheless, there are cases of the so-called non-constituent coordination, where the conjoined expressions are not constituents in the classical sense: 'John met Jane yesterday and Chris today', 'John read a book about linguistics on Mon day and a jour󰏿 nal about computers on Tuesday' (Left-node raising) , 'John made and Peter.painted a wooden chair (Right-node raising). The most common solution is to postulate extra-grammatical levels of representation and/ or special purpose parsing algorithms. There have been a number of proposals within the categorial framework, however, that deal with such phenomena at a grammatical level, extending the number of rules or the set of basic operators. The combinatory rules of type raising and functional composition [Steedman, 1985], for instance, introduce associativity in the structural resources of the grammar. [Dowty, 1988] uses these rules to assign a category to the coordinated conjuncts. With the exception of [Wittenburg and Wall, 1990], that proposes a (less intuitive) normal form for such rules that avoid spurious ambiguity, all the proposals suffer from intractability of the parsing task. Signif icantly, none of them includes, to our knowledge, a formal differentiation between default and exceptional rules. We will consider here a particularly simple account for non-constituent coordination phe nomena based on the sequence product operator introduced in [Solias, 1993]. Its reformulation as a generic rule will show the advantages of expressing default and exceptional grammar rules. . In the non-constituent coordination examples above, we may consider 'Jane yesterday', 'a book about linguistics on Tuesday', etc, as being tuples of expressions belonging to the tuple product. 4• In this case the conjunction scheme type (x \ x)/x would substitute a sequence product by the variable x. In order to introduce this operator we need to extend the basic string algebra of types by adding a tuple operation. Thus the algebra would be (L *, +, (., .) ), being + the concatenative and associative operation and (., .) the operation of tuple formation. The model-theoretic definition for the sequence product is• as follows: D((A,B)) = {< x1,x2 >: X1 E D(A),x2 E D(B)} The sequent rules corresponding to 11 are: r ⇒ A �⇒BR() r,� ⇒ (A,B) r,A,B,� ⇒CL() r,(A,B),�⇒C (11) (12) Examples with more than two elements in the sequence product will need a generalization of the tuple operation. This generalization is straightforward using the standard definition of n-tuple: < x1, ... , Xn >=< < x1, ... , Xn-l > Xn >. Now we are able to account for a sentence like 'John read a book about linguistics on Monday and a journal about computers on Tuesday' by usirig a 3-tuple (np, pp, (np \ s) \ (np \ s)). Right-node raising examples proceed in a similar way. This approach avoids using type-raising (a rule that can be applied on any category at any time), but still suffers from intractability, as it is available for every combination of types. Again, the problem relies on the exceptional status that should be given to the rules that deal with non-canonical phenomena. 4For these simplest cases of Non-constituent coordination we may also use Lambek's associative product. However the introduction of the sequence product brings advantages in more intricate examples of coordination like the ones considered in [Solias, 1993]. Therefore we will use the sequence product in consideration of further extensions of this work. 106 4 A Generic Rule to Parse Non-Constituent Coordination The framework of generic rules offers a natural way to express the grammar to deal with non constituent coordination as an arrangement of default rules, where each combination of types is performed according to the most specific rule available. The essential rules we want to express are: • By default, two types are combined using functional application and, if functional appli󰐀 cation is not applicable, they cannot be combined. • When we try to combine two or more verbal complements and there is a conjunction inmediately preceding them, a sequence product can be formed with them. • When we try to combine a noun phrase and a verb followed by a conjunction, a sequence product can be formed with them. "Verbal complement", for our present purposes, stands for a np, a vm or, in turn, a sequence product 5. Such rules would guarantee that a sequence product is formed only in the relevant cases. We only need an additional rule to scan optimally the elements that match the sequence product on the left-side of the coordination. The formalism of generic rules allows for a direct specification of such set of -still very informal -rules. Once turned into a generic rule, they can be parsed with any bottom-up context-free recognition algorithm (reformulated as the shift-reduce parsing in section 2.4). The first step is to express the operations related to the grammar as binary rules: fa: X/Y Y ➔ X I<-··): canj X Y ➔ canj (X, Y) ha: Y Y\X ➔ X D(···): (X1 · · ·Xn) ➔ X1 · · ·Xn scan: Xn ((X1 · · · Xn-1) Xn)\(X1 · · · Xm) ➔ (X1 · · · Xn-1)\(X1 · · · Xm) (13) fa and ha are the usual forward and backward application rules. I(···) is the rule to introduce a sequence product. As stated, it seems a context-sensitive rule: The formation of a sequence product is only possible when a conjunction is present to the left of the elements that form a sequence product 6• However, this context-sensitivity does not overcome context-free grammar parsing, as the licensipg element is a lexical item, a terminal, and its presence can be checked in constant time. I(···) rule implements the stepped application of rules L/ and R() in the cancellation of type ( (A, B) \ (A, B)) / (A, B) A, B. scan matches elements to the left of the conjunction with the items in the tuple built to the right. This reformulation is intended to a) keep the binary rules arrangement to allow easy formulation of the generic rule, and b) take into account the asymmetry between the formation process for the right and the left coordinated conjuncts 7 • The necessity of bulding a tuple is given by the right conjunct, and the left conjunct is built only to match the right one. scan is implementing the consecutive application of L\ and R(). D(···) is the rule to eliminate the tuple operator and it implements the L() rule. The crucial point to write a generic rule based upon the rules above is to determine the types of the arguments associated to each operation. By default, any combination of categories is driven by functional application rules: forward application (fa) and backward application (ha). Therefore, the first partial rule would be licensed on arguments of the most general type T. This rule will try to apply fa or ha , and will return ..l if both fail, forbidding that combination. 5We use vm as an abbreviation for (np\s)\(np\s). In this application we are only taken under consideration the possibility of having types np and vm as verbal complements. This set should be extended if some other kind of complementation were considered. 6 As [Solias, 1992] pointed out, the conjunction licenses type sequences. Therefore, sequence product can appear in coordination environments, whereas other categories do not. 7The stepped cancellation of the right and the left conjuncts has well-known linguistic motivation, first stated in [Ross, 1967]. 107