B Wang

V Frémont

S A Rodríguez

Color-based Road Detection and its Evaluation on the KITTI Road Benchmark

Keywords: Road detection, Color images, binary map, confidence map, KITTI-ROAD benchmark

Road detection is one of the key issues of scene understanding for Advanced Driving Assistance Systems (ADAS). Recent approaches has addressed this issue through the use of different kinds of sensors, features and algorithms. KITTI-ROAD benchmark has provided an open-access dataset and standard evaluation mean for road area detection. In this paper, we propose an improved road detection algorithm that provides a pixel-level confidence map. The proposed approach is inspired from our former work based on road feature extraction using illuminant intrinsic image and plane extraction from v-disparity map segmentation. In the former research, detection results of road area are represented by binary map. The novelty of this improved algorithm is to introduce likelihood theory to build a confidence map of road detection. Such a strategy copes better with ambiguous environments, compared to a simple binary map. Evaluations and comparisons of both, binary map and confidence map, have been done using the KITTI-ROAD benchmark.

I. INTRODUCTION

Nowadays, Advanced Driving Assistance Systems have achieved great developments, and several new algorithms have been proposed to obtain a better understanding of the environment, in order to improve traffic safety and efficiency. Road detection is one of the key issues of environment understanding for intelligent vehicles. Many approaches that have been developed, involve many kinds of sensors like lidar, radar, camera; many different features like texture features [START_REF] Hui | General road detection from a single image[END_REF], [START_REF] Graovac | Detection of Road Image Borders Based on Texture Classification[END_REF], and spatial feature [START_REF] Kuehnl | Spatial ray features for real-time ego-lane extraction[END_REF]; and different algorithms like optical flow [START_REF] Yoshizaki | Free Space Detection from Catadioptric Omnidirectional Images for Visual Navigation using Optical Flow[END_REF], or neural networks [START_REF] Alvarez | Road scene segmentation from a single image[END_REF]; even the results presentations are various: perspective mapping [START_REF] Wang | Fast road detection from color images[END_REF], occupancy grid [START_REF] Perrollaz | Using the disparity space to compute occupancy grids from stereovision[END_REF], and bird eye view mapping [START_REF] Kuehnl | Spatial ray features for real-time ego-lane extraction[END_REF], [START_REF] Fritsch | A new performance measure and evaluation benchmark for road detection algorithms[END_REF]. Most of these approaches are evaluated on different datasets with different measurements. Fortunately, [START_REF] Fritsch | A new performance measure and evaluation benchmark for road detection algorithms[END_REF] has introduced an open-access dataset and benchmark which is called KITTI-ROAD for road area detection. They also provide a web interface to evaluate road detection approaches in the 2D Bird's Eye View (BEV) space.

In recent years, many vision-based road detection approaches have been proposed such as [START_REF] Hui | General road detection from a single image[END_REF], [START_REF] Graovac | Detection of Road Image Borders Based on Texture Classification[END_REF], [START_REF] Alvarez | Road detection based on illuminant invariance[END_REF]. The versatility of vision systems provides rich information like colors, shapes, and depth at low cost with reduced power consumption. However, vision-based systems are sensible to illumination conditions such as shadows, back-lighting and low rising sun conditions. In [START_REF] Wang | Fast road detection from color images[END_REF], a stereo vision based fast road detection approach has been proposed to handle this problem. It uses the illuminant invariance theory on color images to extract road surface feature, and classify the pixels using confidence interval, finally a stereo vision based road profile extraction helps to confirm the detection result. However, in real traffic scenario, especially with unstructured road, a simple binary classifier presents some limits. Ambiguities often happen in the real driving scene. To handle this issue, we proposed a likelihood-based algorithm which provides a confidence map of the detection result inspired by [START_REF] Wang | Fast road detection from color images[END_REF]. In [START_REF] Wang | Fast road detection from color images[END_REF], there are two main parts in the algorithm: pre-detection from illumination intrinsic image and plane extraction from the v-disparity map segmentation. The idea is to build a likelihood for each pixel after these two main procedures, and to calculate a confidence map by fusing the two likelihood results. The objective is to show that the confidence map should be more flexible than a simple binary map in complex environments.

Both the results of binary map and confidence map are evaluated on the KITTI-ROAD benchmark [START_REF] Fritsch | A new performance measure and evaluation benchmark for road detection algorithms[END_REF]. The evaluation results support our hypotheses in the sens that the confidence map is more adaptive to ambiguous scenery, while binary map outperforms in regular road scenes configuration. Comparisons are also made with the other algorithms published on the KITTI-ROAD website. Our binary map take the second place in F-measure, and the confidence map algorithm still needs to be improved.

The paper is organized as follows: Section II gives a general description of the fast road binary map generation algorithm; in Section III, a likelihood-based road confidence map generation algorithm is introduced in details with a discussion of its application. Section IV shows the experiment results and their evaluation on the KITTI-ROAD benchmark. Finally, a conclusion is given in Section V.

II. FAST ROAD DETECTION WITH BINARY MAP

As described in [START_REF] Wang | Fast road detection from color images[END_REF], the method pipeline starts with a first processing for sky and shadows removal applied to the dataset. An image conversion into a log-chromaticity space provides an efficient and stable identification (i.e. illuminant invariant) of road surface intrinsic features. Then, sample pixels are randomly selected from an assumed "road" area. Next, a confidence interval is defined using the samples to classify pixels of the intrinsic image into the road and nonroad surfaces. Finally, stereo-vision based extension grants access to the 3D road profile estimation and enhances the detection precision. The whole system is show in Fig. 1

A. Illumination intrinsic image generation

In feature-based detection, shadows usually lead to wrong detections. Therefore, invariance properties to illumination conditions must be extracted.

Firstly, a geometric mean based log-chromaticity space is built from the RGB information of the color images [START_REF] Finlayson | Intrinsic images by entropy minimization[END_REF]. In order to avoid favoring one particular channel, the R, G, B factors are divided by their geometric mean.

c i = R i /C ref where, C ref = 3 √ R * G * B (1)
where, c i defined as the chromaticity, is then transformed into log space as ρ i = log(c i ). The color space ρ is orthogonal to u = 1/ √ 3(1, 1, 1) T . Therefore, the transformation from the original coordinates to the geometric mean divided space is given by:

χ ≡ U ρ, χ is 2 × 1 (2)
where U = [v 1 , v 2 ] T , and

v 1 = (1/ √ 2; -1/ √ 2; 0), v 2 = (-1/ √ 6; -1/ √ 6; 2/ √ 6).
Thus, the two dimensions of χ form a log-chromaticity space. In this space, the pixels on the same surfaces under different illuminations build a straight line. The lines which represent different surfaces are almost parallel, Fig. 2. Their directions only correspond to the spectral power distribution. Their displacements are only related to the surface spectral reflectance function [START_REF] Wang | Fast road detection from color images[END_REF]. Hence, an image I θ with suppressed shadows, can be obtained by projecting the lines on their common orthogonal axis which make an angle θ with the horizontal axis.

I θ = χ 1 cos θ + χ 2 sin θ (3)
Entropy minimization [START_REF] Lu | Entropy minimization for shadow removal[END_REF] is used to find the correct axis θ (see Fig. 2). After the geometric log-space transformation and projection onto this axis, as a result, the image I θ is lighting independent and is also shadow-free.

In this research, the calibrated angle is defined off-line to reduce time consumption. The result can be directly used for various driving scenes [START_REF] Alvarez | Road detection based on illuminant invariance[END_REF]. Thus, as a preparation work, calibration could be carried out, and would not affect the realtime detection performance. The algorithm is summarized in [START_REF] Wang | Fast road detection from color images[END_REF].

B. Confidence interval-based pre-detection

Practical fast road detection should be adaptive to dynamic environment. For this reason, it is necessary to reduce the dependency on the prior knowledge about road's ground truth. From this consideration, confidence interval theory is introduced and helps to determine an interval [λ 1 , λ 2 ] to separate the pixels into road or non-road class.

Since I θ has eliminated the influence of shadows, the histogram composed by pixels on road surface is expected to be uni-modal with low dispersion and skewness. Therefore, the normalized histogram follows the empirical form of a normal distribution for a random variable, i.e. I θ (road) ∼ N (µ, σ 2 ). In the KITTI-ROAD dataset, there exist several surfaces similar to road surface, and in order to correctly separate them, a lower confidence level 1 -α = 0.75 is applied to calculate the confidence interval

[λ 1 = µ -0.6745 σ √ n , λ 2 = µ + 0.6745 σ √ n ] of I θ (road).
On image I θ , pixels whose grayscale values fall outside this interval, are considered as background or obstacles. Therefore the classifier is redefined as:

I R = 1 Road, if λ 1 ≤ I(p) ≤ λ 2 I R = 0 non Road, otherwise (4)
Eq. 4 is a classifier, and provides binary images of road detection results. Because the thresholds are based on a confidence level, some pixels can be mis-classified. Holes filling and 'majority' morphological operations can cope with false negative errors. For the false positives, we need fusion information to refine them. This is how stereo vision works in the proposed algorithm, see Section II-C.

Notably, when the vehicle stops right behind the front vehicle, the assumption of bottom road may not stand. For videos or continuous image sequences, a tracking processing is recommended to detect this situation. However, for the dataset composed of discrete frame from different sequence like KITTI-ROAD, it is still a tough issue need to be discussed. A possible way to solve this problem is using disparity region regroup to decide if the bottom area is on a quasi vertical plane or quasi-horizontal plane which helps instructing sample selecting region.

C. Road extraction by stereo vision

In this paper, the former method presented in Section II-B is employed with stereo vision to assist the plane extraction and conversely the v-disparity map helps to correct the falsedetected pixels.When driving in a complex environment, especially in urban scenery, artificial constructions are all along the road, where the materials are possible to show a similar intrinsic feature with the road surface. In this case, only confidence interval based classification is not enough to exclude these artificial structures, while in disparity map, these buildings represent obvious difference with road structure. Thus, stereo vision helps decreasing the false positive detection.

With two images of the same scene captured from slightly different viewpoints, a disparity map I∆ can be computed. I v ∆ is called the v-disparity map and is built by accumulating the pixels of same disparity in I∆ along the v-axis [START_REF] Pritchard | Cloth parameters and motion capture[END_REF]. A projected plane in the v-disparity image follows the equation:

∆ = aυ + b (5)
Thus, for the road plane profile, the disparity value is linearly related to the v-axis.

In the difference of classical methods [START_REF] Soquet | Road segmentation supervised by an extended v-disparity algorithm for autonomous navigation[END_REF], [START_REF] Musleh | Uv disparity analysis in urban environments[END_REF], only the pixels classified as road area in the binary image I R will be accumulated to the disparity map in our algorithm. The limitation of Region-of-Interest (ROI) (where, I R = 1) will greatly reduce the run-time consumption. Reminding that I R gives an pre-detection of drivable road area, most of the obstacles (e.g. buildings and pedestrians) can be avoided in the v-disparity computation. Thus, a regular sloping line as a representation of the drivable area is achieved as shown in Fig. 4. According to Eq.5 which is extracted by the Hough Transform, the ground plane of image I G could be constructed by:

if ∆ p ∈ [∆ υ ± ε υ ], I G = 1, else, I G = 0 (6)
Where, ε υ = c•v is a dynamic variance, which depends on v with a constant scale factor c. The variable c is a positive parameter which indicates that the closer the layout is, the greater the variance becomes. It is determined by preserving the pixels in a 0.95 leveled confidence interval. The variance of disparity on each line is calculated during the accumulation which is used to calculate a proper factor c. Once the parameter is fixed, it is adaptable to most of the driving scenes. Finally, the intersection of I G and I R represent a double verified road detection result, i.e.

I f inal = I R ∩ I G .
However, the v-disparity maps are not always as ideal as expected. Walk sides, or the deformation of the road edge (usually depression) represent a bunch of lines slightly different from road profile in v-disparity space. Fortunately, they only take a small portion of the ROI. A dominate factor preservation step is added to refine the road profile in v-disparity image. The three upper images in Fig. 4 shows comparison of v-disparity images before and after preserving pixels with high intensity values. As a result, the line indicating road profile becomes more clear and precise.

Fig. 3 shows the final result of the algorithm integrated with illumination invariant image, confidence interval and vdisparity map. This result is represented in form of a binary map, which means there is no need for further training or threshold determination on this detection result.

III. LIKELIHOOD METHOD WITH CONFIDENCE MAP

Binary map detection result requires a strict precision of each parameter in the algorithm. However, in some other cases, even the same road might be composed of different materials with different surface textures. Thus, we not only need to be able to separate the surfaces different from road but also need to be tolerant to different textures on the same road. This would be a cruel request for binary map detection. To solve this problem a confidence map is built to provide a more flexible and still reliable road detection result. A confidence map might be much more practical in unstructured roads and high variability in scene layout and in strong changes of illumination conditions.

For generating a confidence map of the road surface, we introduced the concept of likelihood in both the pre-detection processing (Section II-B) and plane extraction processing (Section II-C) in Fig. 1.

A. Likelihood distribution of pre-detection

As in Section II-B, a pre-detection binary image I R is obtained from the intrinsic image I θ . As mentioned above, there exist surfaces with similar intrinsic features to the road surface, and also the road surface itself might show different textures caused by materials, extreme illumination conditions like over-saturation. The former problem will lead to false positive detection, and the latter one will cause false negative detection. To deal with these two conflicting situations in a robust algorithm, a likelihood value is assigned to each pixel of I R with a 3-by-3 filter matrix composed of 1. For every pixel, the likelihood is calculated by the sum of its neighbors in the 3-by-3 operator, and then normalized:

L R (v, u) = v+1 i=v-1 u+1 j=u-1 I R (i, j)/9 (7)
Since I R is a binary image, only the valid pixels (where, L R = 1) after pre-detection will be accumulate to the likelihood computation. The more valid pixels around, the more likely they are on the road surface. As to the false positive pre-detected pixels, they are commonly spread sparsely. After filtered by the operator, they are distributed only with a small likelihood value. On the other hand, for the false negative predetected pixels, they can gain some likelihood values thanks to their correctly detected neighbors. Thus, Eq.7 successfully transforms a binary result into likelihood distribution map.

B. Likelihood distribution of plane extraction

During the driving scene, the stereo baseline is not always parallel to the ground. Hence, the ground plane represented in the picture might be non-horizontal. For example, the left side is lower/higher than the right side. In this case, the disparity plane values along the image u-axis are not centered around a specific value ∆ υ , but differ in a broader range, as shown in Fig. 4. The disparity value of plane pixels stands on the same row v of the image, is more likely following an uniform distribution, thus, a dominant disparity value with high intensity does not exist, Fig. 5. Also, it is hard to define a range of disparity values along the road profile in the vdisparity map.

When there is an obstacle along the road standing on the lower side of ground plane, the disparity value of the obstacle might give ambiguity in the v-disparity accumulation. As in Fig. 4, the upper line shows an image taken by non-horizontal cameras. Right next to the image, the v-disparity map extracted from pre-detection result is illustrated. A bunch of lines spread almost uniformly in a broad range. After the refinement step for preserving dominant disparity values along the v-axis, two lines appear causing an ambiguous situation. Hence, a simple binary classifier is not enough to handle this problem. Firstly, the range of disparity values on the plane [∆ υ ± ε υ ] is widen, so it is possible to have misdetected obstacles as road surface, as long as their disparity value falls into this wide range. Secondly, the disparity value corresponding to the v-axis ∆ υ might even deviate by a wrong Hough line extraction. However, building a complex binary classifier is time consuming, and probably need to verify multiple cues like road's topological and morphological characters. For example, the continuity of the pixels disparity value on the same v-axis might need to be considered.

Another way is to build a likelihood distribution for plane extraction, which measures the deviation of the disparity values to its expectation ∆ υ . Since the dominant value extraction is not reliable, another criterion need to be proposed. The median factor is a proper candidate for the new criterion ∆ υ . It is because road is a sloping plane, then disparity on it on the same v-axis should follow a uniform disparity. Notice that the v-disparity map is built on pre-detected result of Section II-B, even if there exist bias and noise, the median value will fall on the ground plane. For reducing the influence of false positive pre-detection, and speed up the algorithm, only the biggest connected component in I R is preserved as a new Region-of-Interest I new_ROI .

In binary map detection algorithm, a range of disparity values along v-axis is calculated as [∆ υ ±ε υ ], but here:

∆ υ = median(∆(p v )) , ∆(p v )
is the disparity value of the pixels on the v th row of the image and p v ∈ I new_ROI . Pixels are detected as road surface in I R , if their disparity value fall out of this range. Then, they will be distributed with a likelihood value depending on their disparity difference to ∆ υ .

L G (v, u) = (1-| ∆ I R (v, u) -∆ v | /∆ v ) (8)
With Eq.8, every positive pixels in I R has a value up to 1; then we add a unit step function to eliminate those negative likelihood. Thus, we get a likelihood map of ground plane L G within the range of [0,1];

L G = 1 2 L G • (1 + sgn(L G )) (9)

C. Confidence map generation

With the two likelihood maps L R and L G , a confidence map of road detection could be generated based on the following fusion function:

L C (v, u) = L R (v, u) • L G (v, u)
Thus, every potential road surface pixel has been distributed with a confidence value. After an evaluation on the training set of KITTI-ROAD benchmark, a best threshold for the confidence value will be found. Fig. 5 compares the detection performance of binary map and confidence map on the non-horizontal image presented in Fig. 4. In Fig. 5, the binary map detection result is deviated due to the ambiguity of the road profile line in v-disparity map. On contrary, in confidence map, every pixel that is likely to be on the road is presented with a confidence value. After applying a proper threshold on the confidence map, the road area is very well classified. Therefore, confidence map is more reliable in complex situation.

Furthermore, the introduction of a confidence map not only provides a good development based on the original algorithm, but also provides a compatible result with the other algorithms have been evaluated on the KITTI-ROAD benchmark.

IV. EVALUATION RESULTS AND DISCUSSIONS

The two algorithms in this paper are evaluated on the KITTI-ROAD benchmark [START_REF] Fritsch | A new performance measure and evaluation benchmark for road detection algorithms[END_REF]. It contains three different categories of road scenes: UU -urban unmarked road, UMurban marked two direction road and UMM -urban multiple marked lanes' road. The whole dataset has 600 annotated training and test images captured from broad spectrum of urban road scenes. Binary map detection (BM) is evaluated both on training dataset in perspective space and on testing dataset in Bird Eye View (BEV) space, see Fig. 6. Considering the confidence map (CM) generation function is an ongoing research which still needs to be improved, here, we only evaluate it on training dataset as a reference to binary map and baseline algorithm. Perspective evaluation is carried out on a local machine. Bird Eye View results are evaluated on KITTI web server.

Our local processing platform is a standard PC with Windows 7 Enterprise OS, Intel CPU of 2.66 GHz. The computation environment is MATLAB R2013b. The run-time for binary map method is about 2s per frame. A complete confidence map generation algorithm takes about 4s per frame. To speed up the algorithm, we add a processing of maximum connected area preservation, which is firstly used in the ROI calculation to reduce the calculation area for plane extraction. Secondly it is used in the final result definition to refine the result. We also improved the code in details, that is how the computing time is reduced by a factor two from [START_REF] Wang | Fast road detection from color images[END_REF].

A. Binary map evaluation

In the KITTI-ROAD benchmark, the images are selected from different sequences, which demands a more reliable detection result for single images. However, it leads to a problem for usual axis-calibration. The intrinsic angles are different from sequences according to changes in the camera parameters. In the test with UM dataset, axis-calibration varies from images to images, while for the UMM dataset it does not change a lot. This is why our algorithm performs better on UMM dataset in Tab I. In order to provide a reliable result on KITTI-ROAD benchmark, the ground truth of the training dataset is used to calculate the axis angle θ, which is approximately equal to 33°. Detection results are evaluated by F-measure, average precision, accuracy, and other standard measures like: precision, recall and false positive/negative rate.

Methods listed in Tab I are Spatial ray classification (SPRAY [START_REF] Kuehnl | Spatial ray features for real-time ego-lane extraction[END_REF]); Convolutional neutral network (CNN [START_REF] Alvarez | Road scene segmentation from a single image[END_REF]) and Base line (BL), they all have been introduced in [START_REF] Fritsch | A new performance measure and evaluation benchmark for road detection algorithms[END_REF]. In the comparison, binary map detection (BM) performs the best in the measurement of recall and false negative rate. However, since the intrinsic features with a high confidence level detect every possible pixels on the road, in some special situations, binary map will simply lead to false positive detection, for example, when sidewalk shows similar intrinsic features with the road surface, it has a strong probability of being detected as road area. In general, binary map detection methods provides a relative high value on F-measure among the compared algorithms in BEV space. According to the F-measure, fast road detection from color image in binary map won the second place comparing with the other algorithms mentioned in [START_REF] Fritsch | A new performance measure and evaluation benchmark for road detection algorithms[END_REF]. The strength of binary map is its independency from prior knowledge of ground truth: it doesn't need PR curve analysis for a satisfying threshold of confidence. This makes it a portable algorithm which can be applied directly into dynamic environment.

B. Confidence map evaluation

Considering that the KITTI-ROAD dataset is composed of discrete frames from different sequences, (in different weather condition, with different camera parameters), a higher confidence level is assigned during the pre-detection step for likelihood distribution. Thus, more potential road surface pixels will be taken into consideration.

It is interesting that the average precision of the binary map generation algorithm is quite low, which can be hardly compared to the other algorithms. Actually, this measurement, average precision, is a description of Precision-Recall curve with different thresholds to classify the confidence maps. While the binary map directly provides a definite Precision and Recall value, this measurement might not be suitable for it. Under this consideration, we develop the confidence map based on original algorithm so to evaluate our approach on this measure. According to the evaluation result in perspective view (Tab II), the confidence map greatly improved the average accuracy of the detection compare to binary map. Even though, the performance of confidence map general compared to binary image and baseline, it still shows great potential developing space to provide reliable results in complex environment, as been proved in Fig. 5.Besides, in the subset of UMM, confidence map even overpass the baseline. If the confidence map algorithm is improved further more, a good performance is promising , and the evaluation in BEV space will be proceeded later.

V. CONCLUSION

In this paper, we proposed a novel method which combined likelihood theory with our former work presented in [START_REF] Wang | Fast road detection from color images[END_REF]. The results of the original algorithm using a binary map and the improved one based on a confidence map are evaluated on the KITTI-ROAD benchmark. The experimental results show that the binary map provides a high value on the Fmeasure compare to the other algorithms (second place, only behind the SPRAY algorithm). Another strong point of this algorithm is it can provide a straightforward information of free road area without any training. Nevertheless, when drive in complex environments, the detection performance using the binary map falls sharply. As an improved approach, the likelihood-based confidence map performs better in these situations, such as non flat road surface and over-saturation images. However, according to the general evaluation result, there are still improvements need to be done for confidence map estimation. From this consideration, our future works will focus on the likelihood model construction.

Figure 1 .

 1 Figure 1. System of the fast road detection algorithm from color image

Figure 2 .

 2 Figure 2. Axis calibration in log-chromaticity space. Left image: example of chromaticities for 6 surfaces under 9 lights in log-chromacity space; Right image: Entropy plot along angle axis.

Figure 3 .

 3 Figure 3. Binary map detection results on the KITTI-ROAD dataset. Each line presents two images from UM, UMM and UU dataset separately.

Figure 4 .

 4 Figure 4. Examples of v-disparity map in different situations (selected from UU dataset in KITTI-ROAD). Up left : Image of which stereo baseline is not parallel to the ground plane. Bottom left : Image taken from common situation. Middle: v-disparity maps generated from pre-dected ROI. Right: refined v-disparity with high intensity pixels preserved.

Figure 5 .

 5 Figure 5. Detection results of non-horizontal image. Up left: Disparity map of the non-horizontal image presented in Fig.4. Up right: Binary map generate by original algorithm (Section II), which, directly represents the road detection result. Bottom left: Confidence map generated by improved algorithm (Section III). Bottom right: Road detection result by applying a proper threshold on confidence map (CM).

Figure 6 .

 6 Figure 6. Detection results transformed in Bird Eye View (BEV) space.

Table II RESULTS

 II [%] OF PIXEL-BASED ROAD AREA EVALUATION ON TRAINING .13 94.70 79.00 82.67 3.42 17.33 BM 62.53 94.19 73.44 89.07 5.02 10.93 CM 75.88 71.48 93.18 72.53 79.55 4.69 20.45

				SET.
			UM perspective space
	Fmax	AP	Acc	Prec.	Rec.	FPR FNR
	BL 89.27 92.18 96.53 88.93 90.17 2.26	9.83
	BM 85.67 72.21 94.89 77.83 95.26 5.18	4.74
	CM 81.69 80.46 94.09 81.06 82.33 6.67 17.67
		UMM perspective space
	Fmax	AP	Acc	Prec.	Rec.	FPR FNR
	BM 88.76 81.29 94.55 87.04 90.55 4.20	9.45
	CM 85.28 82.08 92.99 85.09 85.46 4.67 14.54
	BL 82.81 89.21 91.23 77.54 88.86 8.02 11.14
			UU Perspective space
	Fmax	AP	Acc	Prec.	Rec.	FPR FNR
	BL 80.79 86


Kahane Sylvain
email: sylvain@kahane.fr

Modyco

Predicative Adjunction in a Modular Dependency Grammar

This paper shows how to introduce predicative adjunction in a dependency grammar inspired from TAG, MTT and RG. The addition of predicative adjunction allows us to obtain a modular surface syntactic grammar, the derivation structures of which can be interpreted as semantic representations.

Introduction

The dependency grammar we propose is inspired by TAG [START_REF] Joshi | Introduction to Tree Adjoining Grammar[END_REF], MTT [START_REF] Mel | Dependency Syntax: Theory and Practice[END_REF] and Relational Grammar [START_REF] Perlmutter | Relational grammar[END_REF]. Like TAG, we combine elementary tree structures in order to generate the surface syntactic structures of sentences. Also like TAG, we want our derivation structures to be interpretable as semantic structures [START_REF] Rambow | A formal look at dependency grammars and phrase-structure grammars, with special consideration of wordorder phenomena[END_REF][START_REF] Candito | Can the derivation tree represent a semantic graph? An answer in the light of Meaning-Text Theory[END_REF]. Like MTT, our syntactic structures are dependency trees and our semantic structures are graphs of predicate-argument relations between the lexical and grammatical meanings of the sentence. Like RG, the syntactic structures are constructed by strata and a syntactic function can be revaluated. Such a formalism has actually already been fully established (see [START_REF] Nasr | A Formalism and a Parser for Lexicalised Dependency Grammars[END_REF][START_REF] Kahane | A fully lexicalized grammar for French based on Meaning-Text theory[END_REF][START_REF] Kahane | Meaning-Text Unification Grammar: Modularity and polarization[END_REF][START_REF] Lareau | Vers une grammaire d'unification Sens-Texte du français : le temps verbal dans l'interface sémantique-syntaxe[END_REF]. [START_REF] Kahane | Polarized Unification Grammars[END_REF] exlores the underlying formalism, which we call Polarized Unification Grammar (PUG), and shows that rewriting systems (including CFG), TAG, HPSG or LFG can be strongly simulated by PUG.

In this paper, we propose to write a PUG with rules (i.e. elementary structures) that are simple (from a mathematical point of view), but that cover rather complex linguistic phenomena, like extraction and complex determiners. The grammar makes extensive use of predicative adjunction, an operation borrowed from TAG for combining structures. Predicative adjunction adjoins the syntactic governor to a node, which means that the syntactic governor is the semantic modifier of its dependent [START_REF] Shieber | An alternative conception of tree-adjoining derivation[END_REF]. As far as we know, the formalism we propose is the first genuine dependency grammar using predicative adjunction. With the help of predicative adjunction, elegant rules are possible that directly interpret the derivation structure as a semantic representation.

The base formalism

Polarized Unification Grammar (PUG) generates a set of finite structures by combining elementary structures. A structure is based on objects, for instance, on nodes and dependencies in a dependency tree. Objects are linked to three kinds of elements: 1) other objects (like a dependency to its source and target nodes), 2) atomic values (labels or feature values), and 3) polarities. Polarities differ from atomic values in the way they combine.

When two (elementary) structures combine, at least one object of a structure must be identified with an object of the other structure (like with TAG substitution, whereby the root of one tree is identified with a leaf of the other tree). When two objects are identified, all the elements linked to them must be combined: objects and values are identified (this is traditionally called unification in unification-based formalisms), while polarities combine by a special operation called the product on polarities. We consider three polarities in this paper: □ = white = unsaturated; ■ = black = saturated; ■ = grey = invisible. Only the white polarity can combine with other polarities and white is the identity element of the product:

• □ ■ ■ □ □ ■ ■ ■ ■ ⊥ ⊥ ■ ■ ⊥ ⊥
Polarities can be interpreted as follows. White objects are unsaturated: they absolutely must combine with a non-white object. A final structure derived by the grammar must not contain any white object. Black objects are the elements of the structure constructed by the grammar. Grey objects are introduced during the derivation but are "invisible" in the end. 1 Fig. 1 proposes five rules for our dependency grammar. These rules are based on Nasr 1995, with improvements proposed by [START_REF] Kahane | Meaning-Text Unification Grammar: Modularity and polarization[END_REF]. Lexemes are represented by nodes and labeled with small capitals (SLEEP, BOY…). Syntactic dependencies are represented by downward pointing arrows. A third kind of objects, represented by diamonds, correspond to grammemes, that is, to what are more or less inflectional morphemes [START_REF] Mel | Dependency Syntax: Theory and Practice[END_REF]. The rule R SLEEP i n d i c a t e s t h a t t h e l e x e m e SLEEP needs a nominal subject and a mood (mood includes finiteness and its value can infinite as well as indicative). The subject dependency and the lexeme (polarized in black) are built by the rule, while the noun and the mood (polarized in white) are requests. The rule R indicative gives a verb the indicative mood 1 It is possible to write a powerful grammar using only black and white polarities. A grey object is in fact a saturated object that is invisible for the other modules of the grammar -for instance, the topological module ensuring the linearization of the syntactic tree. Each dependency thus bears a special polarity (called an interface polarity) indicating to the topological module whether it needs to be linearized or not [START_REF] Kahane | Meaning-Text Unification Grammar: Modularity and polarization[END_REF]. From this point of view, a grey object in the present grammar is an object the interface polarity of which is saturated [START_REF] Lareau | Vers une grammaire d'unification Sens-Texte du français : le temps verbal dans l'interface sémantique-syntaxe[END_REF]. Conversely a black object in the present grammar is visible, that is, it is an object the interface polarity of which is white and must be saturated by the topological module. and says that the indicative must combine with tense. 2 The rule R BOY introduces the noun BOY and asks for definiteness and number for it. Note that the request for a grammeme of definiteness forces the noun to take a determiner. The rule R definite adjoins THE to a noun and gives it a clear value for definiteness. The rule R LITTLE adjoins LITTLE to a noun. These five rules can combine together, as suggested in Fig. 1 (cf. dashed arrows), yielding the dependency tree in Fig. 2. The result of such a derivation is called a derived structure. Note that the tree in Fig. 2 is not saturated. It needs to combine with at least two more rules that introduce tense on SLEEP and number on BOY. We have also simplified the rule for the indicative mood: this mood not only asks for a tense, but for person and number agreement. In a PUG, it is easy, by using a dedicated polarity, to ensure that the structure is a tree and to specify which node is the root [START_REF] Kahane | Polarized Unification Grammars[END_REF]. This point will not be developed here however. 3 Worth is noting that our formalism is not unlike other unification-based formalisms such as HPSG. The schema in Fig. 3 can be easily interpreted as a (recursive) feature structure and a dependency grammar of the kind presented here can be implemented in an HPSG-like formalism [START_REF] Kahane | On the Status of Phrases in Headdriven Phrase Structure Grammar: Illustration by a Fully Lexical Treatment of Extraction[END_REF]. Conversely, HPSG can be strongly simulated by PUG [START_REF] Kahane | Polarized Unification Grammars[END_REF]. (mood, tense…). These objects have their own polarities and values in turn. When the rules R SLEEP and R indicative are combined, two nodes are identified and the values of the maps pol, pos and mood common to both of them are unified. The values of the map mood and tense are objects, so they must be identified and their own maps unified and so on. 4The structure showing the way of how the rules combine in a derivation is called a derivation structure (see Vijay-Shanker 1992 for TAG). We consider three ways of combining rules. The first way is by substitution: R BOY substitutes in R SLEEP because R BOY saturates a leaf of R SLEEP 's structure. The second way is by adjunction: R LITTLE a djoins to R BOY b e c a u s e R LITTLE adds a dependency to a black node of R BOY 's structure. 5 The third way is grammatical completion: R definite completes R BOY by saturating a grammeme in R BOY 's structure. Fig. 4 shows the derivation structure associated with the derivation suggested in Fig. 1 giving the derived structure in Fig. 2. We adopt the following conventions: a substitution is represented by a downward arrow, an adjunction by an upward arrow, and an inflectional completion by a horizontal arrow. With these conventions, the derivation structure can be interpreted as a graph of predicate-argument relations (as shown in [START_REF] Candito | Can the derivation tree represent a semantic graph? An answer in the light of Meaning-Text Theory[END_REF] for TAG) and is the basis for a semantic representation (see [START_REF] Mel | Semantics: From Meaning to Text[END_REF]. Indeed, each arrow in the derivation structure can be interpreted as a semantic dependency that points from a predicate to one of its arguments.

To conclude this section, it must be remarked that we focus on the syntax-semantics interface in this paper and we do not discuss word order. Gerdes & Kahane 2001 propose a formalism-topological grammar-for linearizing dependency trees, even for languages with non-projective constructions. It is possible to write a topological grammar in PUG and to combine it with the grammar presented here (see [START_REF] Kahane | Meaning-Text Unification Grammar: Modularity and polarization[END_REF] for the combination of different modules in PUG).

Dependency rules

The first improvement to the base grammar that we propose is to separate the rules associated with the lexemes proper from the dependency rules ensuring the realization of a given dependency (see the nodal vs. sagittal rules of Kahane & Mel'čuk 1999). We modify our previous rules as a consequence and add separate rules for dependencies. See The dependency rule D subject constrains the subject dependency to be saturated only if the verb has the indicative or subjunctive mood. If 6 We will use the following conventions to name our rules: L for rules instantiating a lexeme, D for a dependency, G for a grammeme and S for structural rules that do not instantiate any object. R is an umbrella identifier used in Section 2, when lexical rules and dependency rules were not separated. 7 In fact, a black dependency has to combine with a white one (if not, a second subject relation could be added to a verb). This can be easily solved by adding a second polarity: every black dependency will have a white additional polarity, while a white dependency will have a black one (see also positive and negative polarities in [START_REF] Kahane | Polarized Unification Grammars[END_REF]).

(V) mood ind/subj SLEEP (V) mood R SLEEP R LITTLE R indicative R BOY R definite
the subject requirement is lexical (the subject is the first actant of the verb, cf. Tesnière 1959), the subject realization is controlled by the mood (mood includes finiteness) (cf. the position of the subject under IP in X-bar syntax). When the verb has another mood, like infinitive or participle, the subject requirement of L SLEEP is not realized by a dependency on SLEEP. For instance, with a progressive form (is sleeping), the subject is lifted to the auxiliary BE. The subject requirement of SLEEP unifies with a grey polarity (and becomes invisible for other modules) and is replaced by a subject dependency on BE. Fig. 6 shows the rule (G progressive ) and the result of its combination with L SLEEP (L SLEEP ⊕ G progressive ). 8 Figure 6. Invisible dependency. 9

The fact that our formalism allows us to suppress a dependency and to replace it with another one is similar to what is proposed by RG. This leads us to consider deep and surface functions (Fillmore 1968). A surface function appears in a surface syntactic tree. A surface function must have been instantiated by a saturation rule, like D subject for the subject function (Fig. 5). A deep function is the initial function received by a lexeme, which can have been instantiated into an identical surface function or which may have been made invisible and replaced by another function.

Some deep functions will never be instantiated as surface functions. This is the case with 8 A similar rule has been proposed by [START_REF] Kahane | A fully lexicalized grammar for French based on Meaning-Text theory[END_REF], where a grey dependency is called a quasi-dependency. The idea to consider a quasi-dependency as a dependency with a saturated interface polarity occured later [START_REF] Kahane | Meaning-Text Unification Grammar: Modularity and polarization[END_REF] and is explained in Lareau 2008. 9 We do not represent grey objects in derived structures in order to simplify the figures and to emphasize the fact they are invisible for further treatments.

the to-obj of TALK, which must be marked by the preposition TO. Fig. 7 shows the rule for the lexeme TALK and the to-obj dependency, as well as their combination (L TALK ⊕ D to-obj ). The last schema in Fig. 7 is a part of the derivation structure of the sentence Aya talks to Bob; it shows that L BOB combines directly with L TALK , while D to-obj is not interpreted as a lexical rule (TO is only a syntactic marker), but as a revaluation of the connection between two lexical rules. Such a rule is ignored when the derivation is interpreted at the semantic level. We choose not to introduce TO in the elementary structure of TALK contrary to what is done in TAG or in previous versions of our dependency grammar [START_REF] Kahane | A fully lexicalized grammar for French based on Meaning-Text theory[END_REF]. We want our grammar to be as modular as possible, separating everything that can be separated. The government markers must be separated from the lexemes that call them for at least two reasons:

• they can be repeated in coordination:

Aya talks to Bob and to Dave.

• they can have an alternative realization; for instance, in French, an indirect object is marked by the preposition À for a noun phrase, but by the dative case for a clitic pronoun (Fig. 8). 10 In English, a complementizer can be realized or not: Aya knew (that) Bob came. Therefore, we want the government markers to be realized by separate rules, but, for semantic reasons, we also want a predicative lexeme to combine directly with its arguments. We have solved these constraints thanks to the grey polarity and the invisible objects; as is shown in Fig. 7, the verb TALK has a direct connection with its semantic argument and it is only in the derived structure that the preposition appears between the verb and its argument.

The case of adjectives is interesting. Adjectives occur in two basic constructions. In the attributive construction they modify a noun (the red book) and in the predicative construction they form a verbal complex with the copula (the book is red). In both cases, 'red' is a semantic predicate and 'book' is its semantic argument. But some adjectives take an event as argument and this argument can be realized by a verb (reading this book is tough). Such adjectives cannot modify their verbal argument, but the direct object of this argument can be promoted (so-called tough-movement) and become the syntactic governor of the adjective (a book tough to read). According to these facts, we cannot assume that the attributive construction is the base construction of every adjective, since this construction is impossible for adjectives taking a verbal argument. We thus propose that, in its base construction, the argument of the adjective has a special deep function we call subj' (Fig. 9). This deep function does not exist as a surface function, but at least three constructions can apply to it: the attributive construction (D subj' ), the predicative construction (S copula ) and the construction of tough-movement (S tough-mvt ). Note that the at-tributive construction can only apply if the argument is realized as a noun or after toughmovement, which promotes a noun as subj'. Intermediate conclusion: Thanks to the grey polarities, which allow us to make an object invisible (for other modules) and to replace it with another configuration, we are able to separate the rules describing the various constructions associated with a lexeme from the rule describing the lexeme itself. In a lexicalized grammar like TAG, an elementary structure describes a lexeme with one of its constructions and the set of elementary structures associated to a given lexeme must be generated by another module (like a metagrammar in [START_REF] Candito | A principle-based hierarchical representation of LTAGs[END_REF]). An advantage of the approach presented here is that the rules associated with the lexemes and their constructions are in the same formalism. They can be precompiled to obtain a lexicalized grammar or they can be triggered on-line during text analysis or synthesis. We will now see how grey polarities can be used for modeling another way of combining lexemes: predicative adjunction.

Complex determiners

Numerous determiners are idiomatic constructions like loads of in ( 1):

(1) Aya read loads of books.

Such a construction causes a mismatch between the syntactic and the semantic structures: loads is the syntactic head of the NP loads of books and thus the syntactic dependent of read, but 'book' is its semantic head and the argument of 'read'. As a consequence, we want the derived tree and the derivation structure of (1) to be as in Fig. 11 (besides S insertion , which is a technical rule introduced below). This problem can be solved by predicative adjunction, as in the standard analysis of complex determiners in TAG [START_REF] Shieber | An alternative conception of tree-adjoining derivation[END_REF]. A predicative adjunction is an adjunction where the adjunct is inserted in the syntactic governor position. This is making possible in our formalism by way of a special rule, S in- sertion , allowing the insertion of a node and a dependency between two other nodes (Fig. 12). This rule can be compared to a rule like D to-obj , which introduces a marker. But S insertion is a generic rule that can apply on any dependency ($r is a variable) and does not replace it but only inserts a dependency [insert:+] be- 11 We have simplified the derived tree by suppressing the attribute before the grammemes.

hind. The formalism forces us to replace the $r dependency by a new one, but in fact we just want to "move" it to a new dependent. The predicative adjunction is indicated by a downward arrow in the derivation structure, like a substitution (Fig. 11). A purely structural rule like S insertion , which does not saturate any object, is represented by a dashed arrow. Note that L BOOK substitutes in L LOADS-OF like in a normal substitution. Consequently, L BOOK substitutes in two rules (L READ and L LOADS-OF ), which is made possible by S insertion . It is important to note that it is BOOK and not LOAD that fulfill the object position of READ. Therefore determiners that (predicatively) adjoin do not need to be nouns. In French there is a productive construction where the complex determiner is an adverb governing the noun (trop de N 'too_much of N', moins de N 'less of N' …). It is also possible to treat simple determiners, including articles, as syntactic governors of the noun they determine [START_REF] Abney | The English Noun Phrase in its Sentential Aspect[END_REF][START_REF] Hudson | Language Networks: The New Word Grammar[END_REF]. But even if in read a book the determiner A becomes the governor of BOOK, it is the noun of the unit a book that will combine with READ and it is not really legitimate to consider a book as a DP.

Note that the rule S insertion can be applied recursively, as in more than half of all known species are insects; indeed half of predicatively adjoins to all known species and more than predicatively adjoins to half.

Extraction

We will focus on relative clauses and start with wh-relative clauses, that is, with relative clauses marked by a wh-word, like in (2):

(2) (the guy) who I invited.

A relative clause depends on a noun (here guy), which is the antecedent of a wh-word (here who). Each wh-word will have its own 12 Again the preposition (of in loads of books) is added by a separated rule. (N) indef pl rule: the rule S WHO attaches the wh-word WHO to a noun bearing the feature +human (Fig. 13). The rule D wh-rel allows predicative adjunction on a wh-word. 13 The rule D rel instantiates the dependency between the antecedent noun and the relative clause and forces the head of the relative clause to be a finite verb in the indicative or subjunctive mood (Fig. 14). Tesnière 1959 argues that the wh-word occupies two positions in the dependency structure: it is both a complementizer (thus being the syntactic head of the relative clause) and a pronoun (filling the "extracted" position) (see additional arguments in [START_REF] Kahane | A propos de la position syntaxique des mots qu[END_REF]. Even though the wh-word occupies only the pronominal position in the derived tree in our account, the wh-word directly attaches to the antecedent noun (see S WHO in Fig. 13 and in the derivation structures of Fig. 14 and16) and thus carries out a complementizer role. It is even possible to not make invisible the wh-rel dependency between the antecedent noun and the wh-word and to obtain a dependency structure similar to Tesnière's stemma for extraction. 13 We could have proposed a rule directly combining S WHO and D wh-rel , as it was done in previous works (Kahane 2001).

It has been well established since Ross 1967 that the string of dependencies between the antecedent noun and the "extracted" position (that is, the position filled by the wh-word) is potentially unbounded but nevertheless very constrained. In (3), the verb THINK has been added in the relative clause and has become the syntactic head of the clause.

(3) (the guy) who you think I invited. Such a verb is called a bridge verb. We introduce a new rule, S unbounded , allowing the predicative adjunction of a bridge verb (Fig. 15). Note that only syntactic dependencies labeled [bridge:+] can be inserted behind a dependency labeled [unbd:+]. This is comparable to the LFG's functional uncertainty [START_REF] Kaplan | Long-distance dependencies, constituent structure, and functional uncertainty[END_REF], where the constraints on extraction are also controlled at the syntactic function level. In the derivation of (3), who adjoins on GUY and substitutes into the object position of INVITE (Fig. 16). The latter is then inserted between WHO and GUY thanks to S wh-rel , which introduces a rel(ative) dependency. In the same Our analysis of wh-relative clauses is similar to the TAG analysis, where the bridge verbs predicatively adjoin [START_REF] Kroch | Analysing Extraposition in a TAG[END_REF]. It can also be compared to the analysis in other frameworks, in particular to LFG with the functional uncertainty, to the generative grammar with Move α, or to HPSG with the slash feature. Contrary to the Move α or slash analyses, it is not the wh-word that is moved, but the bridge verbs that are inserted, like in the functional uncertainty. Moreover, it is not the verb THINK t h a t i s a b r i d g e , b u t o n l y i t s o b j e c t dependency, like in LFG again [START_REF] Kaplan | Long-distance dependencies, constituent structure, and functional uncertainty[END_REF]). Nevertheless, S unbounded is a rule that moves the rel dependency from INVITE to THINK, which can be seen as movement of the complementizer role of the wh-word.

We will now contrast wh-relatives with thatrelative clauses, like (4):

(4) (the guy) that you think I invited.

It has often been argued that that-relatives are syntactically different from wh-relatives, because 1) THAT also marks complement clauses (you think that I invited this guy), 2) it does not accept pied-piping (the guy to whom I speak vs. *the guy to that I speak), 3) that-clauses alternate with unmarked clauses (the guy you think I invited), and 4), contrarily to wh-words, THAT does not have a "human" feature. Consequently, THAT is not analyzed as a pronoun like wh-words, but only as a complementizer, which marks the subordination of a finite clause. We thus necessitate different extraction rules for that-relatives, where the antecedent noun directly fills the "extracted" position: D obj-extraction and D subj-extraction (Fig. 17 With this new set of rules we obtain a different syntactic structure (Fig. 18): THAT is the syntactic head of the relative clause and contrarily to WHO, THAT does not fill the "extracted" position and does not combine with INVITE in (4). THAT only intervenes to mark the subordination of the relative clause. The case of French confirms the relevance of the distinction between wh-relatives and that-relatives. French has a +human wh-word QUI, comparable to WHO, but which can only be used after a preposition (la fille à qui je parle 'the girl to whom I talk'). In case of object extraction, the relative clause is marked by (5) (la fille) que je pense qui m'a invité the girl that I think that invited me 'the girl that I think invited me'

In ( 5), the subject of the complement clause is extracted, but, contrarily to what might have been expected, the marker of the relative clause is QUE (la fille que …) and moreover the marker of the complement clause is QUI (je pense qui …). As a consequence, we can conclude that QUE and QUI are not exactly the subject and object relative markers and that they are not selected according to the "extracted" position they fill. We propose rather that these markers are selected according to the verb they complementize: QUI complementizes a verb without a realized subject, while QUE must complementize a verb with a subject. Such a solution can only be implemented in our formalism if QUI and QUE are treated as markers and connected to the verb they complementize in the syntactic tree (which is not the case for WHO i n o u r a n a l y s i s ) . C o n s equently, we propose subject and object extraction rules for French similar to the rules for English (of Fig. 17), but we add a ±subject feature on the subordinated verb indicating whether its subject has been extracted or not (D subj-extraction in Fig. 19). The QUI marker can only mark a relative clause if the main verb of the clause is [subj:-] (D qui-relative in Fig. 19).

The rule for relatives marked by QUE i s similar (D que-relative in Fig. 20); the only difference is that the verb must have its subject and be marked [subj:+]. The rules for QUI and QUE could be merged assuming that qui and que are two forms of a same lexeme with an opposition of case (nominative for qui and oblique for que) [START_REF] Kahane | A propos de la position syntaxique des mots qu[END_REF]. Moreover the two rules for QUE (D que-relative and D que-complement in Fig. 20) are almost identical: only the syntactic functions involved change. This corroborates Kayne's hypothesis that all these complementizers are one and the same.

Conclusion

We have presented a dependency grammar that constructs syntactic dependency trees like any other dependency grammar. But this grammar accomplishes more than others. First, it takes into account the syntax-semantics interface: the derivation structure can be interpreted as a graph of predicate-argument relations, that is, as the skeleton of a semantic representation (in the sense of [START_REF] Mel | Dependency Syntax: Theory and Practice[END_REF][START_REF] Mel | Semantics: From Meaning to Text[END_REF]. Second, this grammar accomodates the syntax-text interface, that is, linearization and morphology. Even though the linearization rules are not presented here (see [START_REF] Kahane | Meaning-Text Unification Grammar: Modularity and polarization[END_REF][START_REF] Gerdes | Tree Unification Grammar Problems and Proposals for Topology, TAG, and German[END_REF] for linearization rules in PUG), it could be shown that the derived structure contains all the surface syntactic dependencies necessary to calculate the linear order [START_REF] Gerdes | Word Order in German: A Formal Dependency Grammar Using a Topological Hierarchy[END_REF].

In other respects, the grammar presented here is very modular. Grammatical constructions have their own independent rules, separated from the lexical rules, which describe only the base construction of lexemes. From this point a view, this grammar enters in the paradigm of construction grammars (CxGs) and can even be seen as a formalization of the Relational Grammar [START_REF] Perlmutter | Relational grammar[END_REF].

Our formalism makes a big use of the invisible polarity and the predicative adjunction. Formally, the derived structure is a graph with (V) ind/subj a tree skeleton, which is the visible part of the derived structure (the objects polarized in black). The fact that we constantly maintain a tree skeleton during the derivation process is probably an important property from a computational point of view, but this has not been investigated further and the formalism has not been implemented.

Figure 1 .

 1 Figure 1. Sample rules and combination

Figure 2 .

 2 Figure 2. A (non-final) derived structure

Figure 3 .

 3 Figure 3. Our conventions 3 Fig. 3 makes our formal conventions more precise. A black node has black polarity. The

  2

  value of a map we call pol. The lexeme name and the part of speech (pos) are atomic values. Grammemes are objects linked to the lexeme node by a map labeled by the name of the inflectional category

Figure

  Figure 4. Derivation structure

  Figure 5. Lexical vs. dependency rules 7

Figure 7 .

 7 Figure 7. Governed preposition.

  Figure 8. Indirect object in French

Figure 9 .

 9 Figure 9. Adjectival constructionsThe same deep function subj' is used for the passive past participle, which can enter into a predicative construction (a book has been stolen) or an attributive construction (the book stolen by Bob). The passive construction marked by the past participle inflection can be derived from a verbal base form by a rule using grey polarities again (Fig.10).

Figure

  Figure 10. Passive voice

Figure 11 .

 11 Figure 11. Derived tree and derivation structure for (1) 11

Figure 12 .

 12 Figure 12. Predicative adjunction 12

Figure 13 .

 13 Figure 13. Rules for wh-relatives

Figure 15 .

 15 Figure 15. Rules for bridge verbs

  substitutes in the object position of THINK. As the object dependency bears a feature [bridge:+], the rule S unbounded can apply and insert THINK between GUY and INVITE, replacing the rel relation by a new one. This can be done recursively. At the end, the rel dependency is instantiated by D rel .

  ). Subject and object extraction are differentiated because 1) only the object extraction really accepts the predicative adjunction of bridge verbs ( ? *the guy that you think that invited me), and 2) only the object extraction can be unmarked (He is the guy *(that) invited me). Consequently, only D obj-extraction c a n c o m b i n e w i t h S unbounded a n d D unmarked-relative .

Figure 17 .

 17 Figure 17. Rules for that-relatives

  can be compared to THAT (le livre que je lisais 'the book that I read'); in particular, QUE i s a l s o t h e m a r k e r o f c o m p l e m e n t clauses (tu penses que j'ai invité ce gars 'you think that I invited this guy') and no piedpiping is possible with QUE. Subject extraction is marked by a QUI form, different from the other QUI, because this one is not +human (le livre qui est là 'the book that is there'). Kayne 1975 argues that QUE is always a pure complementizer, even when it marks relative clauses. His main argument is the so-called qui-que alternation:

Figure 19 .

 19 Figure 19. Rules for qui-relatives

We have slightly simplified Fig.3. A map host from each grammeme to its lexeme is needed in order to ensure that the identification of two grammemes entails the identification of their host lexemes.

 5 This kind of adjunction is called sister adjunction by[START_REF] Rambow | Dtree grammars[END_REF]. Contrary to predicative adjunction, sister adjunction does not change the weak generative capacity of the formalism. One can note that the distinction between substitution and adjunction is small in PUG: in both cases, a black and a white node are identified. The only difference is the direction of the dependency, which is not really relevant in PUG (source and target are interchangeable from a graph-theoretical perspective).

The two constructions of PARLER'talk' are: (i) Aya parle à Bob 'Aya talks to Bob' (ii) Aya lui parle 'Aya talks to him'

Acknowledgments

I would like to thank Kim Gerdes, François Lareau and Tim Osborne for many valuable comments and corrections.