High-throughput DNA and RNA sequencing has become a routine experiment in molecular biology and life sciences in general. It is increasingly used in the hospital as a key procedure of personalized medicine.

Compared to the second generation, third generation sequencing technologies produce longer reads with comparatively lower throughput and higher error rate. Those errors include substitutions, indels, and they hinder or at least complicate downstream analysis like mapping or de novo assembly. However, these long read data are often used in conjunction with short reads of the 2nd generation.

I will present a hybrid strategy for correcting the long reads using the short reads that we introduced last year. Unlike existing error correction tool, ours, called LoRDEC, avoids the alignment of short reads on long reads, which is computationally very intensive. Instead, it takes advantage of a succinct graph to represent the short reads, and compares the long reads to paths in the graph. Experiments show that LoRDEC outperforms existing methods in running time and memory while achieving a comparable correction performance. In conclusion, i will comment on the impact of read error correction.

Work in collaboration with L. Salmela from University of Helsinki. LoRDEC is available at: http://www.lirmm.fr/~rivals/lordec/

  LoRDEC: a tool for correcting errors in long sequencing reads Montpellier Omics Days 2016 Eric Rivals, LIRMM & Institut de Biologie Computationnelle (IBC) CNRS et Université de Montpellier, France


LoRDEC experimental results Impact of parameters Scalability Correction of transcriptomic reads (RNA-seq) Correction of Oxford Nanopore MINIon reads LoRDEC * +LoRMA LoRMA experimental results Conclusion and future works

LoRDEC *

Build a de Bruijn graph of the LONG reads

Use a small k such that the genomic k-mers are expected to be found in the reads Use an abundancy threshold to differentiate between correct and erroneous k-mers

For each long read:

Classify k-mers: solid (= in the DBG) and weak Find paths in the DBG between the solid k-mers Minimize edit distance between the long read and the path's string Select a correcting path only if all possibilities have been explored.

LoRDEC

  Build a de Bruijn graph of the short readsFor each long read:Classify k-mers: solid (= in the DBG) and weak Find paths in the DBG between the solid k-mers Minimize edit distance between the long read and the path's string

Rivals (CNRS Univ. Montpellier)Long read correction 7th Nov. 2016

build a de Bruijn graph of the short reads the graph represents the short reads in compact form

take each long read in turn and attempt to correct it 1 correct internal regions, 2 correct end regions of the long read Rivals (CNRS Univ. Montpellier) Long read correction 7th Nov. 2016

Context

3rd generation sequencing technologies yield longer reads PacBio Single Molecule Real Time sequencing: much longer reads (up to 25 Kb) but much higher error rates Error correction is required 1 self correction: using long reads only 2 hybrid correction: using short reads to correct long reads

Evaluation methods

Two ways:

1 how do the reads align to the genome?

2 how do raw and corrected reads differ in their alignments?

Using the Error Correction Toolkit


Nabil Kahouadji
email: n-kahouadji@neiu.edu

Niky Kamran
email: nkamran@math.mcgill.ca

Keti Tenenblat
email: k.tenenblat@mat.unb.br

LOCAL ISOMETRIC IMMERSIONS OF PSEUDO-SPHERICAL SURFACES AND k-TH ORDER EVOLUTION EQUATIONS

Keywords: evolution equations, pseudo-spherical surfaces, isometric immersions. MSC 2010: 35L60, 37K25, 47J35, 53B10, 53B25

We consider the class of evolution equations that describe pseudo-spherical surfaces of the form ut = F (u, ∂u/∂x, ..., ∂ k u/∂x k ), k ≥ 2 classified by Chern-Tenenblat. This class of equations is characterized by the property that to each solution of a differential equation within this class, there corresponds a 2-dimensional Riemannian metric of curvature -1. We investigate the following problem: given such a metric, is there a local isometric immersion in R 3 such that the coefficients of the second fundamental form of the surface depend on a jet of finite order of u? By extending our previous result for second order evolution equation to k-th order equations, we prove that there is only one type of equations that admit such an isometric immersion. We prove that the coefficients of the second fundamental forms of the local isometric immersion determined by the solutions u are universal, i.e., they are independent of u. Moreover, we show that there exists a foliation of the domain of the parameters of the surface by straight lines with the property that the mean curvature of the surface is constant along the images of these straight lines under the isometric immersion.

Introduction

This paper is the third in a series [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF][START_REF] Kahouadji | Local Isometric Immersions of Pseudo-spherical Surfaces and Evolution Equations[END_REF] in which we consider the special properties of the local isometric immersions into three-dimensional Euclidean space E 3 of the metrics of constant negative Gaussian curvature K = -1 associated to the solutions u of evolution equations

∂u ∂t = F (u, ∂u ∂x , . . . , ∂ k u ∂x k ), (1)
describing pseudo-spherical surfaces. For reasons that will be explained below, our main interest lies in determining evolution equations [START_REF] Beals | Bäcklund transformations and inverse scattering solutions for some pseudospherical surface equations[END_REF] for which the components of the second fundamental form of the local isometric immersion depend on u and finitely many of its derivatives only, in other words on a jet of finite order of u.

Recall following Chern and Tenenblat [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF] that a partial differential equation

∆ t, x, u, ∂u ∂x , ∂u ∂t , . . . , ∂ k u ∂t l ∂x k-l = 0, (2)
belongs to the class of differential equations describing pseudo-spherical surfaces if there exist 1-forms

ω i = f i1 dx + f i2 dt, 1 ≤ i ≤ 3, (3)
where the coefficients f ij , 1 ≤ i ≤ 3, 1 ≤ j ≤ 2, are smooth functions of t, x, u and finitely many derivatives of u with respect to t and x, such that the structure equations

dω 1 = ω 3 ∧ ω 2 , dω 2 = ω 1 ∧ ω 3 , dω 3 = ω 1 ∧ ω 2 = 0, (4)
for a metric of constant Gaussian curvature K = -1 hold if, and only if, u is a solution of [START_REF] Silva | Third-order differential equations and local isometric immersions of pseudo-spherical surfaces[END_REF]. In this case every smooth solution u : U ⊂ R 2 → R of an equation (2) describing pseudo-spherical surfaces defines on U a Riemannian metric

ds 2 = (ω 1 ) 2 + (ω 2 ) 2 , (5)
of constant Gaussian curvature K = -1, with ω 3 being the Levi-Civita connection 1-form of the metric [START_REF] Catalano Ferraioli | Local isometric immersions of pseudospherical surfaces described by evolution equations in conservation law form[END_REF].

An important motivation for the question investigated in this paper comes from the special properties of the sine-Gordon equation

u tx = sin u, (6)
whose well-known integrability properties can be completely accounted for through the perspective of the general theory developed by Chern and Tenenblat. First, it is straightforward to check that the 1-forms

ω 1 = 1 η sin u dt, ω 2 = η dx + 1 η cos u dt, ω 3 = u x dx. (7)
satisfy the structure equations ( 4) whenever u is a solution of the sine-Gordon equation [START_REF] Ferraioli | Fourth order evolution equations which describe pseudospherical surfaces[END_REF]. The non-zero real parameter η appearing in [START_REF] Cavalcante | Conservation laws for nonlinear evolution equations[END_REF] is directly related to the existence of a one-parameter family of Bäcklund transformation and the existence of infinitely many conservation laws for the sine-Gordon equation. It is thus a key ingredient in the solution of the sine-Gordon equation by the method of inverse scattering. More generally one may consider the general class of partial differential equations describing pseudo-spherical surfaces with the special property that one of the components f ij can be chosen to be a continuous parameter. Such equations are said to describe η pseudo-spherical surfaces. The evolution equations (1) describing η pseudo-spherical surfaces have been completely classified by Chern and Tenenblat in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF], whenever f 21 = η, F and f ij depend on u and finitely many derivatives of u with respect to t and x. Any differential equation describing η pseudo-spherical surfaces is the integrability condition of a linear system of the form

dv 1 = 1 2 ω 2 v 1 + (ω 1 -ω 3 ) v 2 , dv 2 = 1 2 (ω 1 + ω 3 ) v 1 -ω 2 v 2 ,
which may be used to solve the given differential equation by the method of inverse scattering [START_REF] Beals | Bäcklund transformations and inverse scattering solutions for some pseudospherical surface equations[END_REF], with η playing the role of the spectral parameter for the scattering problem. It is also shown in [START_REF] Cavalcante | Conservation laws for nonlinear evolution equations[END_REF] that one can generate infinite sequences of conservation laws for the class of differential equations describing η pseudo-spherical surfaces by making use of the structure equations (4), although some of these conservation laws may end up being non-local. Important further developments of these ideas around this theme can be found in [START_REF] Silva | Third order equations describing pseudo-spherical surfaces[END_REF], [START_REF] Catalano Ferraioli | Second order evolution equations which describe pseudospherical surfaces[END_REF], [START_REF] Ferraioli | Fourth order evolution equations which describe pseudospherical surfaces[END_REF], [START_REF] Foursov | On formal integrability of evolution equations and local geometry of surfaces[END_REF]- [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF], [START_REF] Kamran | On differential equations describing pseudo-spherical surfaces[END_REF]- [START_REF] Reyes | Correspondence theorems for hierarchies of equations of pseudo-spherical type[END_REF]. We should also remark at this stage that given a differential equation describing pseudospherical surfaces, the choice of 1-forms satisfying the structure equations (4) is generally not unique. For example the 1-forms given by

ω 1 = cos u 2 (dx + dt), ω 2 = sin u 2 (dx -dt), ω 3 = u x 2 dx - u t 2 dt, (8)
which are different from the 1-forms given in [START_REF] Cavalcante | Conservation laws for nonlinear evolution equations[END_REF], will also satisfy the structure equations ( 4) whenever u is a solution of the sine-Gordon equation ( 6).

Starting with [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF], we have initiated the study of differential equations describing pseudospherical surfaces from an extrinsic perspective, in which we focus on the properties of the local isometric immersions of the metrics (5) associated to the solutions of the equations. It is indeed a classical result that any metric (5) of constant negative scalar curvature can be locally isometrically immersed in E 3 . For the metrics defined by solutions u : U ⊂ R 2 → R of equations describing pseudo-spherical surfaces, it is thus natural to ask in view of the integrability properties enjoyed by this class of equations if the second fundamental form of the immersion can be expressed in a simple way in terms of the solution u. This turns out to be effectively the case for the sine-Gordon equation [START_REF] Ferraioli | Fourth order evolution equations which describe pseudospherical surfaces[END_REF]. Indeed let us first recall the components a, b, c of the second fundamental form of a local isometric immersion of a pseudo-spherical surface into E 3 are defined by the relations

ω 13 = a ω 1 + b ω 2 , ω 23 = b ω 1 + c ω 2 ,
where the 1-forms ω 13 , ω 23 satisfy the structure equations

dω 13 = ω 12 ∧ ω 23 , dω 23 = ω 21 ∧ ω 13 ,
equivalent to the Codazzi equations, and the Gauss equation, given by

ac -b 2 = -1,
for a pseudo-spherical surface. For the sine-Gordon equation, with the choice of 1-forms ω 1 , ω 2 and ω 3 = ω 12 given by ( 8), the 1-forms ω 13 , ω 23 are easily computed to be

ω 13 = sin u 2 (dx + dt) = tan u 2 ω 1 , ω 23 = -cos u 2 (dx -dt) = -cot u 2 ω 2 .
We thus observe the remarkable property that the components a, b, c of the second fundamental form depend only on u through some simple, closed-form expressions. It would therefore not be unreasonable to expect a similar property to hold for all equations describing pseudo-spherical surfaces, where the requirement could be relaxed by allowing the coefficients a, b.c of the second fundamental form to depend on u and finitely many of its derivatives. In [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF][START_REF] Kahouadji | Local Isometric Immersions of Pseudo-spherical Surfaces and Evolution Equations[END_REF], we began to investigate the class of differential equations describing pseudo-spherical surfaces from this extrinsic perspective. Thus in [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF], we proved that for second-order equations of the form

∂u ∂t = F (u, ∂u ∂x , ∂ 2 u ∂x 2 ), and
∂ 2 u ∂x∂t = F (u, ∂u ∂x ),
describing η pseudo-spherical surfaces, the only equations for which a, b, c will depend on u and finitely many derivatives of u are given by the sine-Gordon equation [START_REF] Ferraioli | Fourth order evolution equations which describe pseudospherical surfaces[END_REF], and evolution equations of the form

∂u ∂t = 1 f 11,u f 12, ∂u ∂x ∂ 2 u ∂x 2 + f 12,u ∂u ∂x ∓ (βf 11 -ηf 12 ) , (9)
where f 11,u = 0 and f 12, ∂u ∂x = 0, where in the latter case the components a, b, c of the second fundamental form are universal functions of x, t, independent of u. Results of a similar nature were obtained in [START_REF] Silva | Third-order differential equations and local isometric immersions of pseudo-spherical surfaces[END_REF] for third-order equations of the form

∂u ∂t - ∂ 3 u ∂x 2 ∂t = λu ∂ 3 u ∂x 3 + G(u, ∂u ∂x , ∂ 2 u ∂x 2
). and in [START_REF] Catalano Ferraioli | Local isometric immersions of pseudospherical surfaces described by evolution equations in conservation law form[END_REF] for a class of second order evolution equations of type

∂u ∂t = A(x, t, u) ∂ 2 u ∂x 2 + B(x, t, u, ∂u ∂x )
and for k-th order evolution equations in conservation law form.

In [START_REF] Kahouadji | Local Isometric Immersions of Pseudo-spherical Surfaces and Evolution Equations[END_REF], the same question was considered for the evolution equations (1) of order k ≥ 3 classified in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF], where we proved as a first result that the a, b, c are again necessarily universal functions of x, t, independent of u. Our purpose in the present paper is to complete this analysis by determining the analogue of the form (9) for k-th order evolution equations [START_REF] Beals | Bäcklund transformations and inverse scattering solutions for some pseudospherical surface equations[END_REF]. We now state our main result: Theorem 1. Except for k-th order evolution equations of the form

∂u ∂t = 1 f 11,u k-1 i=0 f 12,∂ i u/∂x i • ∂ i+1 u ∂x i+1 ∓ (βf 11 -ηf 12 ) , k ≥ 2, (10)
where f 11,u = 0 and f 12, ∂ k-1 u ∂x k-1 = 0, there exists no k-th order evolution equation of order k ≥ 2 describing η pseudo-spherical surfaces, with 1-forms (3) given as in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF], with the property that the coefficients of the second fundamental forms of the local isometric immersions of the surfaces associated to the solutions u of the equation depend on a jet of finite order of u. Moreover, the coefficients of the second fundamental forms of the local isometric immersions of the surfaces determined by the solutions u of (10) are universal, i.e., they are universal functions of ηx + βt, independent of u.

This theorem provides further evidence the special place that the sine-Gordon equation appears to occupy amongst all integrable equations from the perspective provided by the theory of differential equations describing η pseudo-spherical surfaces.

We point out that the universal coefficients of the second fundamental forms of the isometric immersions mentioned in Theorem 1 are explicitly given in Proposition 1. We now prove a consequence of our main result.

Corollary 1. For each solution u of an equation of type [START_REF] Foursov | On formal integrability of evolution equations and local geometry of surfaces[END_REF], there exists a foliation of the domain of u by straight lines with the property that when the metric of constant negative Gaussian curvature K = -1 associated to u through ( 5) is locally isometrically immersed as a surface S ⊂ E 3 , the mean curvature of S is constant along the curves defined by the images under the immersion of the lines of this foliation.

Proof. For each solution u of any equation of type [START_REF] Foursov | On formal integrability of evolution equations and local geometry of surfaces[END_REF], the associated 1-forms (3) define a metric with Gaussian curvature K = -1. It follows from Theorem 1 that a local isometric immersion of such a metric into R 3 is determined by the coefficients of the second fundamental form, which are functions of ηx + βt. Now consider (x, t) ∈ R 2 such that the straight line ηx + βt = δ, δ ∈ R is contained in the domain of definition of the immersion. The domain is foliated by such straight lines. For each δ, the image of the straight line is a curve in the surface. Along this curve the coefficients of the second fundamental form are constants determined by δ. Since the mean curvature H of the surface is given by the trace of the second fundamental form, it follows that H is constant along any such curve.

Before proving Theorem 1, we observe that a similar result on the mean curvature of the immersed surface also holds for the main results obtained in [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF] and [START_REF] Silva | Third-order differential equations and local isometric immersions of pseudo-spherical surfaces[END_REF]. In fact, the arguments are the same as those used in the proof of the Corollary above.

Proof of Theorem 1

The proof of Theorem 1 is based on an order analysis of the Codazzi and Gauss equations that govern the local isometric immersions of pseudo-spherical surfaces in E 3 , considering in turn each branch of the Chern-Tenenblat classification of k-th order evolution equations describing η pseudo-spherical surfaces [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF]. In order to carry out this analysis, one should first express these equations in terms of the components f ij of the 1-forms that appear in the formulation of the problem. These conditions have already been worked out in [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF][START_REF] Kahouadji | Local Isometric Immersions of Pseudo-spherical Surfaces and Evolution Equations[END_REF]; the Codazzi equations read

f 11 D t a + f 21 D t b -f 12 D x a -f 22 D x b -2b∆ 13 + (a -c)∆ 23 = 0, (11)
f 11 D t b + f 21 D t c -f 12 D x b -f 22 D x c + (a -c)∆ 13 + 2b∆ 23 = 0, (12)
where

∆ 12 := f 11 f 22 -f 21 f 12 ; ∆ 13 := f 11 f 32 -f 31 f 12 ; ∆ 23 := f 21 f 32 -f 31 f 22 ,
and where the operators D t and D x are total derivative operators, while the Gauss equation is given by acb 2 = -1.

(13) In the case of a differential equation describing η pseudo-spherical surfaces (with f 21 = η), the structure equations ( 4) are equivalent to

D t f 11 -D x f 12 = ∆ 23 , D x f 22 = ∆ 13 , D t f 31 -D x f 32 = -∆ 12 ,
where D t and D x are the total derivative operators and

∆ 12 := f 11 f 22 -ηf 12 = 0, ∆ 13 := f 11 f 32 -f 31 f 12 , ∆ 23 = ηf 32 -f 31 f 22 .
We shall use the notation [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF] to denote the derivatives of u with respect to x and write the evolution equation (1) as z 0,t = F (z 0 , z 1 , . . . , z k ). We will thus think of (t, x, z 0 , . . . , z k ) as local coordinates on an open set of the submanifold of the jet space J k (R 2 , R) defined by the differential equation ( 1). We will use the following lemma from [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF] which expresses the necessary and sufficient conditions for the structure equations ( 4) to hold: Lemma 1. [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF] Let (1) be a k-th order evolution equation describing η pseudo-spherical surfaces, with associated 1-forms (3) such that f 21 = η. Then necessary and sufficient conditions for the structure equations (4) to hold are given by

z i = u x i = ∂ i u ∂x i , 0 ≤ i ≤ k, introduced in
f 11,z k = • • • = f 11,z1 = 0, f 21 = η, f 31,z k = • • • = f 31,z1 = 0, (14) f 12,z k = 0, f 22,z k = f 22,z k-1 = 0, f 32,z k = 0, (15)
f 2 11,z0 + f 2 31,z0 = 0, (16)
f 11,z0 F = k-1 i=0 f 12,zi z i+1 + ηf 32 -f 31 f 22 , (17)
k-2 i=0 f 22,zi z i+1 = f 11 f 32 -f 31 f 12 , (18)
f 31,z0 F = k-1 i=0 f 32,zi z i+1 + ηf 12 -f 11 f 22 , (19)
and

f 11 f 22 -ηf 12 = 0. ( 20
)
As stated in the Introduction, Theorem 1 states that the k-th order evolution equation of type (1) describing η pseudo-spherical surfaces are divided into two categories when viewed from the perspective of the local isometric immersions of pseudo-spherical metrics defined by their solutions: either the coefficients of the second fundamental forms are universal functions of x and t, independent u, or the coefficients of the second fundamental form depend of a jet of infinite order of u. In order to prove our theorem, we shall make use of the classification results for k-th order evolution equations describing η pseudo-spherical surfaces given in Theorems 2.2, 2.3, 2.4 and 2.5 in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF]. These theorems considered five groups of equations, summarized and reorganized below, according to the properties of the following functions first introduced in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF]] 14)- [START_REF] Rabelo | A classification of pseudospherical surfaces equations of the type ut = uxxx + G(u, ux, uxx) which describe pseudospherical surfaces[END_REF], is in one of the following five groups:

H = f 11 f 11,z0 -f 31 f 31,z0 , L = f 11 f 31,z0 -f 31 f 11,z0 , Remark 1. A k-th order evolution equation z 0,t = F (z 0 , ..., z k ) describing η pseudo-spherical surfaces with associated 1-forms ω i = f i1 dx + f i2 dt, 1 ≤ i ≤ 3, where f ij , 1 ≤ j ≤ 2 satisfy (
I: L = 0 with f 31 = λf 11 = 0, λ 2 -1 = 0. In this case, f 22 does not depend on z i , 0 ≤ i ≤ k and f 32 = λf 12 . II: L = 0 with f 31 = λf 11 = 0, λ 2 -1 = 0. In this case, f 22,z k-2 = 0. III: L = 0 and H = 0, i.e., f 11 = 0 and f 31,z0 = 0 or f 31 = 0 and f 11,z0 = 0. IV: L = 0 and H = 0, i.e., f 2 31 -f 2 11 = C = 0. V: HL = 0. We observe that equations of Groups I and II were treated in Theorem 2.4 (a) and (b) in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF] respectively and equations of Groups III, IV and V were treated in Theorems 2.3, 2.5 and 2.2 in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF] respectively.

If the coefficients a, b, c of the 1-forms ω 13 and ω 23 depend of a jet of finite order of u = z 0 , that is a, b, c are functions of x, t, z 0 , . . . , z l for some finite l, then ( 11) and ( 12) become

f 11 a t + ηb t -f 12 a x -f 22 b x -2b∆ 13 + (a -c)∆ 23 - l i=0 (f 12 a zi + f 22 b zi )z i+1 + l i=0 (f 11 a zi + ηb zi )z i,t = 0, and
f 11 b t + ηc t -f 12 b x -f 22 c x + (a -c)∆ 13 + 2b∆ 23 - l i=0 (f 12 b zi + f 22 c zi )z i+1 + l i=0 (f 11 b zi + ηc zi )z i,t = 0.
In [START_REF] Kahouadji | Local Isometric Immersions of Pseudo-spherical Surfaces and Evolution Equations[END_REF], we showed that if the coefficients of the second fundamental form a, b and c depend on a jet of finite order of u = z 0 , then a, b and c are universal, that is l = 0 and a, b and c depend at most on x and t only. Therefore, equations [START_REF] Gomes Neto | Fifth-order evolution equations describing pseudospherical surfaces[END_REF] and [START_REF] Górka | The modified Hunter-Saxton equation[END_REF] become

f 11 a t + ηb t -f 12 a x -f 22 b x -2b(f 11 f 32 -f 31 f 12 ) + (a -c)(ηf 32 -f 31 f 22 ) = 0, (21)
f 11 b t + ηc t -f 12 b x -f 22 c x + (a -c)(f 11 f 32 -f 31 f 12 ) + 2b(ηf 32 -f 31 f 22 ) = 0, (22)
where a x , b x , c x are the partial derivatives of a, b, c with respect to x, and a t , b t , c t are the partial derivatives of a, b, c with respect to t. We now consider in turn all the cases listed in Remark 1 and state the conclusion for each case in the form of a proposition. The first proposition pertains to evolution equations in item I of Remark 1.

Proposition 1. Let ∂u ∂t = 1 f 11,u k-1 i=0 f 12,∂ i u/∂x i • ∂ i+1 u ∂x i+1 ∓ (βf 11 -ηf 12 ) , (23)
where f 11,u = 0 and f 12, ∂ k-1 u ∂x k-1 = 0, be a k-th order evolution equation, k ≥ 2, which describes η pseudo-spherical surfaces with 1-forms ω i as in [START_REF] Chern | Pseudospherical surfaces and evolution equations[END_REF]. There exists a local isometric immersion in R 3 of a pseudo-spherical surface, determined by a solution u, for which the coefficients a, b, c of the second fundamental form depend on a jet of finite order of u if, and only if, the coefficients are universal and are given by

a = le ±2(ηx+βt) -γ 2 e ±4(ηx+βt) -1, (24) b
= γe ±2(ηx+βt) , (25)
c = γ 2 e ±4(ηx+βt) -1 le ±2(ηx+βt) -γ 2 e ±4(ηx+βt) -1 , (26)
l, γ ∈ R, l > 0 and l 2 > 4γ 2 . The 1-forms are defined on a strip of R where

log l -l 2 -4γ 2 2γ 2 < ±(ηx + βt) < log l + l 2 -4γ 2 2γ 2 . ( 27
)
Moreover, the constants l and γ have to be chosen so that the strip intersects the domain of the solution of the evolution equation.

Proof. For evolution equations of type I, we have f 31 = ±f 11 , f 32 = ±f 12 , f 11,z0 = 0, f 12,z k-1 = 0 and the equation is given by [START_REF] Reyes | Geometric integrability of the Camassa-Holm equation[END_REF]. Moreover, f 22 = β is independent of z 0 , . . . , z k . Equations ( 21) and ( 22) become

f 11 a t + ηb t -f 12 a x -βb x ∓ (a -c)(βf 11 -ηf 12 ) = 0, (28)
f 11 b t + ηc t -f 12 b x -βc x ∓ 2b(βf 11 -ηf 12 ) = 0. (29)
Since k ≥ 2, differentiating the latter two equations with respect to z k-1 leads to

-f 12,z k-1 a x ± (a -c)ηf 12,z k-1 = 0, -f 12,z k-1 b x ± 2bηf 12,z k-1 = 0.
Note that f 12,z k-1 = 0 by hypothesis, which means that these equations simplify to

a x ∓ η(a -c) = 0, (30)
b x ∓ 2ηb = 0. (31)
Taking into account (30) and (31), equations ( 28) and (29) become

f 11 a t + ηb t -βb x ∓ (a -c)βf 11 = 0, (32)
f 11 b t + ηc t -βc x ∓ 2bβf 11 = 0. (33)
Differentiating (32) and (33) with respect to z 0 , with f 11,z0 = 0, leads to

a t ∓ β(a -c) = 0, (34) b t ∓ 2βb = 0, (35)
and hence, (32) and (33) become

ηb t -βb x = 0, ( 36
) ηc t -βc x = 0. ( 37
)
Note that (30) and (34) imply ηa t -βa x = 0.

From (31) and (35), we conclude that

b = γe ±2(ηx+βt) , γ ∈ R. (38)
Note that a = 0. Otherwise, if a = 0, then (30) implies that c = 0 and the Gauss equation leads to b = ±1 which contradicts (31). Therefore, from the Gauss equation we have

c = (b 2 -1)a -1 . (39)
Then, in view of (38), equations (30) and (34) reduce to aa x ∓ η(a 2 -γ 2 e ±4(ηx+βt) + 1) = 0, aa t ∓ β(a 2 -γ 2 e ±4(ηx+βt) + 1) = 0.

The latter system leads then to

a = le ±2(ηx+βt) -γ 2 e ±4(ηx+βt) -1, l ∈ R,
which is defined wherever le ±2(ηx+βt) -γ 2 e ±4(ηx+βt) -1 > 0. Hence l > 0 and

l -l 2 -4γ 2 2γ 2 < e ±2(ηx+βt) < l + l 2 -4γ 2 2γ 2 ,
i.e., a is defined on the strip described by ( 27). Now, from (39), we obtain c = γ 2 e ±4(ηx+βt) -1 le ±2(ηx+βt) -γ 2 e ±4(ηx+βt) -1 .

A straightforward computation shows that the converse holds. Finally, we observe that given a solution of the evolution equation, in order to have an immersion, one has to choose the constants l and γ, such that the strip (27) intersects the domain of the solution in R 2 .

Next, we consider the evolution equations covered in item II of Remark 1.

Proposition 2. For k-th evolution equations, k ≥ 2, describing η pseudo-spherical surfaces with associated 1-forms

ω i = f i1 dx + f i2 dt, 1 ≤ i ≤ 3
, where f 31 = λf 11 = 0, and λ 2 = 1, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

Proof. When f 31 = λf 11 = 0, with λ 2 = 1, the structure equations ( 17), ( 18) and ( 19) can be rewritten as

f 11,z0 F = k-1 i=0 f 12,zi z i+1 + ηf 32 -λf 11 f 22 , (40)
k-2 i=0 f 22,zi z i+1 = f 11 (f 32 -λf 12 ), (41)
λf 11,z0 F = k-1 i=0 f 32,zi z i+1 + ηf 12 -f 11 f 22 = 0. (42)
Differentiating (40) with respect to z k leads to f 11,z0 F z k = f 12,z k-1 . Because f 11,z0 = 0 (otherwise (16) would fail) and F z k = 0 (otherwise F is not a k-th order evolution equation), we conclude that f 12,z k-1 = 0. Subtracting λ times equation ( 40) from (42) leads to

k-1 i=0 (f 32,zi -λf 12,zi )z i+1 + η(f 12 -λf 32 ) + (λ 2 -1)f 11 f 22 = 0. ( 43
)
Differentiating the latter with respect to z k leads to

f 32,z k-1 -λf 12,z k-1 = 0. ( 44
)
Since k ≥ 2, differentiating equation (41) with respect to z k-1 and taking into account (44) leads to

f 22,z k-2 = 0. (45)
Differentiating (43) with respect to z k-1 leads to

f 32,z k-2 -λf 12,z k-2 + η(f 12,z k-1 -λf 32,z k-1 ) = 0. (46)
Substituting f 32,z k-1 by λf 12,z k-1 , which is just equation (44), equation (46) becomes

f 32,z k-2 -λf 12,z k-2 = η(λ 2 -1)f 12,z k-1 .
Because neither of η, λ 2 -1 and f 12,z k-1 is zero, we conclude that when f 31 = λf 11 = 0 and λ 2 = 1, we have

f 32,z k-2 -λf 12,z k-2 = 0.
(47) Consider now equations ( 21) and ( 22), which can be written as follows:

f 11 a t + ηb t -f 12 a x -f 22 b x -2bf 11 (f 32 -λf 12 ) + (a -c)(ηf 32 -λf 11 f 22 ) = 0, (48)
f 11 b t + ηc t -f 12 b x -f 22 c x + (a -c)f 11 (f 32 -λf 12 ) + 2b(ηf 32 -λf 11 f 22 ) = 0. ( 49
)
Differentiating ( 48) and ( 49) with respect to z k-1 and taking into account (45) leads to

-f 12,z k-1 a x -2bf 11 (f 32,z k-1 -λf 12,z k-1 ) + (a -c)ηf 32,z k-1 = 0, -f 12,z k-1 b x -2bf 11 (f 32,z k-1 -λf 12,z k-1 ) + 2bηf 32,z k-1 = 0.
Taking into account (44) and the fact that f 12,z k-1 = 0, these two equations reduce to

a x = (a -c)ηλ, b x = 2bηλ.
Substituting the latter two equations in ( 48) and ( 49) leads

f 11 a t + ηb t -f 12 ηλ(a -c) -f 22 ηλ2b -2bf 11 (f 32 -λf 12 ) + (a -c)(ηf 32 -λf 11 f 22 ) = 0, f 11 b t + ηc t -f 12 ηλ2b -f 22 c x + (a -c)f 11 (f 32 -λf 12 ) + 2b(ηf 32 -λf 11 f 22 ) = 0.
If k ≥ 3, differentiating these two equations with respect to z k-2 leads to

-f 12,z k-2 ηλ(a -c) -2bf 11 (f 32,z k-2 -λf 12,z k-2 ) + (a -c)ηf 32,z k-2 = 0, -f 12,z k-2 ηλ2b + (a -c)f 11 (f 32,z k-2 -λf 12,z k-2 ) + 2bηf 32,z k-2 = 0,
which can be rewritten as

(f 32,z k-2 -λf 12,z k-2 )((a -c)η -2bf 11 ) = 0, (f 32,z k-2 -λf 12,z k-2 )((a -c)f 11 + 2bη).
Since from (47), f 32,z k-2 -λf 12,z k-2 = 0, we can rewrite the two equations in matrix form as follows

η -f 11 f 11 η a -c 2b = 0.
Since f 11,z0 = 0, the determinant f 2 11 + η 2 = 0, and hence ac = b = 0. The latter contradicts the Gauss equation [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF].

When k = 2, the proof of this proposition was given in [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF]. Therefore, we conclude that when f 31 = λf 11 = 0, λ 2 = 1 for any k ≥ 2, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

The following Proposition is concerned with the evolution equations covered by item III of Remark 1.

Proposition 3. For k-th evolution equations, k ≥ 2, describing η pseudo-spherical surfaces with associated 1-forms ω i = f i1 dx + f i2 dt, 1 ≤ i ≤ 3, where either f 11 = 0 or f 31 = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

Proof. i) When f 11 = 0, the structure equations ( 17), ( 18) and ( 19) can be rewritten as follows:

k-1 i=0 f 12,zi z i+1 = -ηf 32 + f 31 f 22 , ( 50
) k-2 i=0 f 12,zi z i+1 = -f 31 f 12 , (51)
f 31,z0 F = k-1 i=0 f 32,zi z i+1 + ηf 12 . (52)
Differentiating (50) with respect to z k leads to f 12,z k-1 = 0. Since k ≥ 2, differentiating (51) with respect to z k-1 , leads to f 22,z k-2 = 0. Differentiating (52) with respect to z k leads to

f 31,z0 F z k = f 32,z k-1 .
On one hand, F z k = 0 because the evolution equation F is of order k. On the other hand, f 31,z0 = 0, otherwise ( 16) is not satisfied. We conclude then that

f 32,z k-1 = 0.
Equations ( 21) and ( 22) become

ηb t -f 12 a x -f 22 b x + 2bf 31 f 12 + (a -c)(ηf 32 -f 31 f 22 ) = 0 ηc t -f 12 b x -f 22 c x -(a -c)f 31 f 12 + 2b(ηf 32 -f 31 f 22 ) = 0
Differentiating the latter two equations with respect to z k-1 leads to

(a -c)ηf 32,z k-1 = 0, 2bηf 32,z k-1 = 0,
and since f 32,z k-1 = 0, we conclude that a-c = b = 0, which contradicts the Gauss equation [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF]. Therefore, for any k ≥ 2, when f 11 = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

ii) When f 31 = 0, the structure equations ( 17), ( 18) and ( 19) can be rewritten as follows:

f 11,z0 F = k-1 i=0 f 12,zi z i+1 + ηf 32 , (53)
k-2 i=0 f 12,zi z i+1 = f 11 f 32 , (54)
k-1 i=0 f 32,zi z i+1 = f 11 f 22 -ηf 12 . (55)
Differentiating (55) with respect to z k leads to f 32,z k-1 = 0. Since k ≥ 2, differentiating (54) with respect to z k-1 leads to f 22,z k-2 = 0. Differentiating (53) with respect to z k leads to

f 11,z0 F z k = f 12,z k-1 .
On one hand, F z k = 0 because the evolution equation F is of order k. On the other hand, f 11,z0 = 0, otherwise ( 16) is not satisfied. We conclude then that

f 12,z k-1 = 0. (56)
Equations ( 21) and ( 22) become

f 11 a t + ηb t -f 12 a x -f 22 b x -2bf 11 f 32 + (a -c)ηf 32 = 0, (57)
f 11 b t + ηc t -f 12 b x -f 22 c x + (a -c)f 11 f 32 + 2bηf 32 = 0. (58)
Differentiating ( 57) and (58) with respect to z k-1 and taking into account (56) leads to

a x = b x = 0
With (56), equations ( 57) and (58) become

f 11 a t + ηb t -2bf 11 f 32 + (a -c)ηf 32 = 0, (59)
f 11 b t + ηc t -f 22 c x + (a -c)f 11 f 32 + 2bηf 32 = 0. (60)
Taking into account the fact that f 32,z k-1 = 0, and then differentiating (55) with respect to z k-1 leads to

f 32,z k-2 = -ηf 12,z k-1
and because neither η nor f 12,z k-1 vanishes, we have

f 32,z k-2 = 0.
If k ≥ 3, differentiating then (59) and (60) with respect to z k-2 , then dividing by f 32,z k-2 , and rewriting the two equations in matrix form, leads to

η -f 11 f 11 η a -c 2b = 0.
Since f 11,z0 = 0, the determinant f 2 11 + η 2 = 0, and hence ac = b = 0, which contradicts the Gauss equation [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF].

If k = 2, the proof of this proposition was given in [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF]. Therefore, we conclude that for any k ≥ 2, when f 31 = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

Next, we consider the evolution equations in item IV of Remark 1.

Proposition 4. For k-th order evolution equations, k ≥ 2, describing η pseudo-spherical surfaces with associated 1-forms ω i = f i1 dx + f i2 dt, 1 ≤ i ≤ 3, where f 2 31 -f 2 11 = C = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

Proof. When f 2 31 -f 2 11 = C = 0, then H = 0 and L = 0. We consider the structure equations ( 17), ( 18) and [START_REF] Rabelo | On equations of the type uxt = F (u, ux) which describe pseudospherical surfaces[END_REF]. On one hand, subtracting f 31 times (19) from f 11 times [START_REF] Rabelo | A characterization of differential equations of type uxt = F (u, ∂u/∂x, ..., ∂ k /∂x k ) which describe pseudospherical surfaces, An[END_REF], and taking into account that H = 0, leads to

k-1 i=0 (f 11 f 12,zi -f 31 f 32,zi )z i+1 + η(f 11 f 32 -f 31 f 12 ) = HF = 0.
Differentiating the latter with respect to z k leads to

f 11 f 12,z k-1 -f 31 f 32,z k-1 = 0. (61)
On the other hand, subtracting f 31 times (17) from f 11 times (19) leads to

LF = k-1 i=0 (f 11 f 32,zi -f 31 f 12,zi )z i+1 + η(f 11 f 12 -f 31 f 32 ) + Cf 22 = 0.
Differentiating the latter with respect to z k leads to

LF z k = f 11 f 32,z k-1 -f 31 f 12,z k-1 .
Note that because neither of L and F z k is zero, we have

f 11 f 32,z k-1 -f 31 f 12,z k-1 = 0. (62)
Observe that since f 2 31 -f 2 11 = C = 0, we conclude that f 11 = 0 and f 31 = 0. In fact, otherwise if f 11 = 0, then f 2 31 = C, which contradicts [START_REF] Kamran | On differential equations describing pseudo-spherical surfaces[END_REF]. Similarly, one shows that f 31 = 0. From (61) and (62), we then conclude that f 12,z k-1 = 0, and f 32,z k-1 = 0. Indeed, if f 12,z k-1 = 0 (resp. f 32,z k-1 = 0) then it follows from (61) that f 32,z k-1 = 0 (resp. f 12,z k-1 = 0) which contradicts (62). We conclude then from (61) that

f 11 f 31 = f 32,z k-1 f 12,z k-1 . ( 63
)
In light of the above analysis, let's consider [START_REF] Reyes | Pseudo-spherical surfaces and integrability of evolution equations[END_REF] and [START_REF] Reyes | Conservation laws and Calapso-Guichard deformations of equations describing pseudospherical surfaces[END_REF]. Since k ≥ 2, differentiating ( 21) and [START_REF] Reyes | Conservation laws and Calapso-Guichard deformations of equations describing pseudospherical surfaces[END_REF] with respect to z k-1 , and then dividing by f 12,z k-1 = 0, leads to

a x = (a -c)η f 32,z k-1 f 12,z k-1 -2b f 11 f 32,z k-1 -f 31 f 12,z k-1 f 12,z k-1 b x = (a -c) f 11 f 32,z k-1 -f 31 f 12,z k-1 f 12,z k-1 + 2bη f 32,z k-1 f 12,z k-1
Taking into account (63) and f 2 31 -f 2 11 = C, these equations reduce to

a x = (a -c)η f 11 f 31 + 2b C f 31 , b x = -(a -c) C f 31 + 2bη f 11 f 31 .
Differentiating the latter two equations with respect to z 0 leads to -ηL(a -c) -Cf 31,z0 2b = 0, Cf 31,z0 (ac) -ηL2b = 0, which in matrix form become -ηL -Cf 31,z0 Cf 31,z0

-ηL

a -c 2b = 0.
Because neither η, C, f 31,z0 and L is zero, the determinant η 2 L 2 + C 2 f 2 31,z0 = 0, and hence ac = b = 0, which contradicts the Gauss equation [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF]. Therefore, we conclude that for any k ≥ 2, when f 2 31 -f 2 11 = C = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent. Finally, we have the following similar result for the evolution equations in item V of Remark 1.

Proposition 5. For k-th order evolution equations, k ≥ 2, describing η pseudo-spherical surfaces of type [START_REF] Beals | Bäcklund transformations and inverse scattering solutions for some pseudospherical surface equations[END_REF], with associated 1-forms ω i = f i1 dx + f i2 dt, 1 ≤ i ≤ 3, where HL = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

Proof. We consider the structure equations ( 17), ( 18) and [START_REF] Rabelo | On equations of the type uxt = F (u, ux) which describe pseudospherical surfaces[END_REF]. We are assuming that HL = 0, where H = f 11 f 11,z0 -f 31 f 31,z0 and L = f 11 f 31,z0 -f 31 f 11,z0 , hence f 11 = 0 and f 31 = 0. Subtracting f 31 times (19) from f 11 times (17) leads to

HF = k-1 i=0 (f 11 f 12,zi -f 31 f 32,zi )z i+1 + η(f 11 f 32 -f 31 f 12 ), (64)
while subtracting f 31 times (17) from f 11 times (19) leads to

LF = k-1 i=0 (f 11 f 32,zi -f 31 f 12,zi )z i+1 + (f 2 31 -f 2 11 )f 22 + η(f 11 f 12 -f 31 f 32 ). (65)
Differentiating ( 64) and (65) with respect to z k leads to

f 11 f 12,z k-1 -f 31 f 32,z k-1 = HF z k , f 11 f 32,z k-1 -f 31 f 12,z k-1 = LF z k ,
and since neither of H, L and F z k is zero, we have

f 11 f 12,z k-1 -f 31 f 32,z k-1 = 0, (66)
f 11 f 32,z k-1 -f 31 f 12,z k-1 = 0. (67)
Since k ≥ 2, differentiating [START_REF] Rabelo | On equations which describe pseudospherical surfaces[END_REF] with respect to z k-1 leads to

f 11 f 32,z k-1 -f 31 f 12,z k-1 = f 22,z k-2 , (68)
and hence

f 22,z k-2 = 0. (69)
Note that when HL = 0, it follows from (64) and (65) that the expression of F can be written in two equivalent ways:

F = k-1 i=0 f 11 f 12,zi -f 31 f 32,zi H z i+1 + η f 11 f 32 -f 31 f 12 H , F = k-1 i=0 f 11 f 32,zi -f 31 f 12,zi L z i+1 + (f 2 31 -f 2 11 )f 22 L + η f 11 f 12 -f 31 f 32 L .
Subtracting the last two equations leads then to

k-1 i=0 f 11 f 12,zi -f 31 f 32,zi H - f 11 f 32,zi -f 31 f 12,zi L z i+1 +η f 11 f 32 -f 31 f 12 H - f 11 f 12 -f 31 f 32 L - (f 2 31 -f 2 11 )f 22 L = 0. (70)
Differentiating this equation with respect to z k leads to

L(f 11 f 12,z k-1 -f 31 f 32,z k-1 ) -H(f 11 f 32,z k-1 -f 31 f 12,z k-1 ) = 0.
Substituting the expressions of H and L in the latter, and after simplifying the expression, leads to

(f 2 31 -f 2 11 )(f 11,z0 f 32,z k-1 -f 31,z0 f 12,z k-1 ) = 0. Note that f 2 31 -f 2 11 is not a constant, otherwise H = 0. We conclude then that f 11,z0 f 32,z k-1 -f 31,z0 f 12,z k-1 = 0. (71)
Note also that f 11,z0 and f 31,z0 cannot vanish simultaneously, otherwise ( 16) is not satisfied. Moreover, f 12,z k-1 and f 32,z k-1 cannot simultaneously vanish, otherwise F is not a k-th order evolution equation. Moreover, [START_REF] Rabelo | A characterization of differential equations of type uxt = F (u, ∂u/∂x, ..., ∂ k /∂x k ) which describe pseudospherical surfaces, An[END_REF] and [START_REF] Rabelo | On equations of the type uxt = F (u, ux) which describe pseudospherical surfaces[END_REF] imply that f 11,z0 = 0 if, and only if, f 12,z k-1 = 0 and f 31,z0 = 0 if, and only if, f 32,z k-1 = 0. Therefore, if f 11,z0 = 0 then f 12,z k-1 = 0, f 31,z0 = 0 and f 32,z k-1 = 0. Similarly, if f 31,z0 = 0, then f 32,z k-1 = 0, f 11,z0 = 0 and f 31,z k-1 = 0.

We now consider equations ( 21) and [START_REF] Reyes | Conservation laws and Calapso-Guichard deformations of equations describing pseudospherical surfaces[END_REF]. Differentiating these equations with respect to z k-1 leads to

f 12,z k-1 a x = (a -c)ηf 32,z k-1 -2b(f 11 f 32,z k-1 -f 31 f 12,z k-1 ), (72)
f 12,z k-1 b x = (a -c)(f 11 f 32,z k-1 -f 31 f 12,z k-1 ) + 2bηf 32,z k-1 . (73)
If f 12,z k-1 = 0, then f 32,z k-1 = 0, and the system of equations ( 72) and (73) becomes

η -f 11 f 11 η a -c 2b = 0.
The determinant η 2 + f 2 11 = 0, and hence ac = b = 0, which runs into a contradiction with the Gauss equation [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF].

If f 12,z k-1 = 0, then the system of equations ( 72) and ( 73) can be rewritten as follows:

a x = (a -c)η f 32,z k-1 f 12,z k-1 -2b f 11 f 32,z k-1 -f 31 f 12,z k-1 f 12,z k-1 , (74)
b x = (a -c) f 11 f 32,z k-1 -f 31 f 12,z k-1 f 12,z k-1 + 2bη f 32,z k-1 f 12,z k-1 . (75)
From (71) and the assumption f 12,z k-1 = 0, we have

f 32,z k-1 f 12,z k-1 = f 31,z0 f 11,z0 .
Substituting the latter in ( 74) and (75) leads to

a x = (a -c)η f 31,z0 f 11,z0 -2b L f 11,z0 , (76)
b x = (a -c) L f 11,z0 + 2bη f 31,z0 f 11,z0 . (77)
Differentiating the latter two equations with respect to z 0 leads to

η(f 31,z0 /f 11,z0 ) z0 -(L/f 11,z0 ) z0 (L/f 11,z0 ) z0 η(f 31,z0 /f 11,z0 ) z0 a -c 2b = 0.
The determinant η 2 (f 31,z0 /f 11,z0 ) 2 z0 +(L/f 11,z0 ) 2 z0 = 0. Otherwise, a-c = b = 0, which runs into a contradiction with the Gauss equation [START_REF] Jorge | Linear problems associated to evolution equations of type utt = F (u, ux, uxx, ut)[END_REF]. Threfore, (f 31,z0 /f 11,z0 ) z0 = 0, and (L/f 11,z0 ) z0 = 0. Note that the vanishing of (f 31,z0 /f 11,z0 ) z0 means that

f 31 = γf 11 + µ, (78)
where γ and µ are constants. We have then f 32,z k-1 f 12,z k-1 = f 31,z0 f 11,z0 = γ and hence f 32 = λf 12 + ν, (79) where ν depends on z 0 , ..., z k-2 . Note that (67) and f 12,z k-1 = 0 means that µ = 0. This fact can also be obtained from the non-vanishing of L = -µf 11,z0 = 0.

(80)

In light of (78), (79) and (80), equations (76) and (77) become Substituting the last four equations in [START_REF] Reyes | Pseudo-spherical surfaces and integrability of evolution equations[END_REF] and [START_REF] Reyes | Conservation laws and Calapso-Guichard deformations of equations describing pseudospherical surfaces[END_REF]

It follows from these equations that ν depends at most on z 0 and -[2bb t + (ac)a t ]f 2 11 -2bη(c t + a t )f 11 + η 2 [(ac)c t -2bb t ] = 0. Therefore 2bb t + (ac)a t = b(c t + a t ) = (ac)c t -2bb t = 0. If b = 0, then a t = 0 and hence c t =0. If b = 0, then c t + a t = 0 and using the derivative of the Gauss equation ( 13), we get that (ac)c t -2bb t = -2a t (ac) = 0. If either a t = 0 or ac = 0, we get a t = c t = 0. Hence, for any b, we have that a and c do not depend on t. It follows from the Gauss equation that b also does not depend on t. Therefore (81) and (82) reduce to ην -f 11 ν f 11 ν ην ac) 2b = 0.

Since ac and b cannot vanish simultaneously, the determinant ν 2 (η 2 + f 2 11 ) = 0. hence ν = 0. The above analysis implies that f 31 = µ = 0, f 32 = 0, H = f 11 f 11,z0 and L = -µf 11,z0 . Therefore, (70) reduces to (µ 2 -f 2 11 )(ηf 12 -f 22 f 11 ) = 0. Differentiating with respect to z k-1 , we get a contradiction since (µ 2 -f 2 11 )f 12,z k-1 = 0. If k = 2, the proof of this proposition was given in [START_REF] Kahouadji | Second-order Equations and Local Isometric Immersions of Pseudo-spherical Surfaces[END_REF]. Finally, we conclude that for any k ≥ 2, whenever HL = 0, the system of equations ( 11), ( 12) and ( 13) is inconsistent.

a

  x = (ac)ηγ + 2bµ, b x = -(a -c)µ + 2bηγ.We have alsof 11 f 32 -f 31 f 12 = νf 11 -µf 12 , ηf 32 -f 31 f 22 = ηγf 12 + ηνγf 11 f 22 -µf 22 .

  leads to f 11 a t + ηb t -(ac)(γf 11 f 22 -ην) -2b(ηγf 22 + νf 11 ) = 0, (81)f 11 b t + ηc t -f 22 c x + (ac)νf 11 + 2b(ηνγf 11 f 22 -µf 22 ) = 0. (82)If k ≥ 3, differentiating (81) and (82) with respect to z k-2 , and then dividing by f 22,z k -2 = 0, leads to(-2bf 11 + (ac)η) ν ,z k-2 f 22,z k-2 = γ((ac)f 11 + 2bη),(83)((ac)f 11 + 2bη) ν ,z k-2 f 22,z k-2 = 2bγf 11 + c x + 2bµ).(84)Observe that -2bf 11 + (a-c)η and (a-c)f 11 + 2bη cannot vanish simultaneously, since f 11,z0 = 0 and (ac) 2 + b 2 = 0. Therefore, from (83) and (84) we getγ[(ac) 2 + 4b 2 ]f 2 11 + [2bηγ(ac) + 2b(c x + 2bµ)]f 11 + 4γb 2 η 2 -η(ac)(c x + 2bµ) = 0.Differentiating twice with respect to z 0 leads to γ = 0 and c x + 2bµ = 0. Hence, (81) and (82) reduce tof 11 b t + ηc t + [(ac)f 11 + 2bη]ν = 0,(85)f 11 a t + ηb t + [-2bf 11 + (ac)η]ν = 0.

Research partially supported by NSERC Grant RGPIN 105490-2011 and by the Ministério de Ciência e Tecnologia, Brazil, CNPq Proc. No. 303774/2009-6.


The assessment of highly-risky situations at road intersections have been recently revealed as an important research topic within the context of the automotive industry. In this paper we shall introduce a novel approach to compute risk functions by using a combination of a highly non-linear processing model in conjunction with a powerful information encoding procedure. Specifically, the elements of information either static or dynamic that appear in a road intersection scene are encoded by using directed positional acyclic labeled graphs. The risk assessment problem is then reformulated in terms of an inductive learning task carried out by a recursive neural network. Recursive neural networks are connectionist models capable of solving supervised and non-supervised learning problems represented by directed ordered acyclic graphs. The potential of this novel approach is demonstrated through well predefined scenarios. The major difference of our approach compared to others is expressed by the fact of learning the structure of the risk. Furthermore, the combination of a rich information encoding procedure with a generalized model of dynamical recurrent networks permit us, as we shall demonstrate, a sophisticated processing of information that we believe as being a first step for building future advanced intersection safety systems.

I. INTRODUCTION

N the last few years a substantial effort of the European Union has been devoted to the organization of resources and the development of a sustainable approach to the prevention of traffic accidents. Moreover, it has been shown [START_REF]CARE Community database on Accidents on the Roads in Europe[END_REF] that traffic accidents have become one of the major causes of death and injury not only in Europe but also globally. In addition, road intersections have been identified as one of the principal scenarios where traffic accidents take place. Several initiatives resulting from a joint effort between the European Union and the automotive industry have recently emerged [START_REF]PReVENT Subproject, Sixth Framework Programme (FP6)[END_REF] [START_REF] Willwarn | PReVENT Subproject, Sixth Framework Programme (FP6)[END_REF]. In this line, the aim of INTERSAFE [START_REF]Requirements for intersection safety applications[END_REF] [START_REF] Ch | Intersection Safety-The EC-Project INTERSAFE[END_REF], a subproject of the IP PReVENT [START_REF]PReVENT European Project[END_REF] project is to improve safety and to reduce fatal collisions at intersections by providing appropriate assistance to the driver. The driver should be warned against potential right of way violations caused by himself or other road-users, including failing to stop at red lights and stop signs, or turning across the path of other traffic. This objective is Manuscript received January 31, 2007. INTERSAFE is a subproject of the IP PReVENT. This work is part of the 6 th Framework Program funded by the European Commission. The partners of INTERSAFE thank the European Commision for supporting the work of this project.

The authors are with INRIA, BP 105, Le Chesnay Cedex, France, Tel. + 33-1-39-63-55-47, Fax: + 33-1-39-63-51-14, e-mail: Alejandro.Chinea_Manrique_De_Lara@inria.fr, Michel.Parent@inria.fr. achieved by the development of risk assessment and data fusion algorithms that use as inputs the information collected from a combination of sensors for detection of vehicles and any other object present in the scene together with sensors for localization of the host vehicle, namely the test vehicle equipped with the INTERSAFE technology.

Highly-risky situations at road intersections are a combination of multiple factors that are very difficult to evaluate. The time-varying and highly non-linear nature of the problem makes extremely difficult to properly model the embeddings of information through time. In this paper, we propose a different point of view to the problem of computing risk functions. Specifically, we interpret the risk as a geometrical object embedded into a space-time manifold. The geometry of the risk is determined by taking into account the combined actions and roles of the objects present at road intersections (i.e. vehicles, pedestrians, traffic lights, trees, buildings and so forth). To this end, a novel information encoding procedure was designed to extract the intrinsic relations between such objects. Specifically, road intersection scenes are encoded by using directed ordered positional acyclic labeled graphs. The nodes of the graphs are labeled in the sense that they contain sets of domain variables represented by an array of numerical and categorical features.

This representation permits to combine disparate source of information (i.e. time and a priori knowledge about the intersection) in a compact structure that allows expressing complex relations between information units that can vary in size, as opposed to feature-based approaches. Once the information has been represented in terms of labeled graphs, the problem of risk assessment is expressed in terms of an inductive learning task performed by a recursive neural network. Recursive neural networks [START_REF] Sperduti | Supervised Neural Networks for the Classification of Structures[END_REF][8] [START_REF] Hagenbuchner | A Self-Organizing Map for Adaptive Processing of Structured Data[END_REF] are highly non-linear adaptive models that are able to learn structured data (i.e. trees or graphs patterns) even if such data is noisy or incomplete. The main motivation of using neural networks is reflected by the fact of being models that are able to recognize patterns we cannot even define. This property is called recognition without definition and it enables intelligent systems (i.e. like humans) to generalize. Namely, the ability to recognize multitudes of unforeseen complex patterns without any ability to define them. In our application, the recursive neural network is trained using a conveniently generated pattern set where each pattern corresponds to a road intersection scene encoded by means of directed ordered acyclic labeled graphs.

The rest of this paper is organized as follows: In the next

Risk Assessment Algorithms Based on Recursive Neural Networks

Alejandro Chinea IEEE member, Michel Parent I section, the problem we address is presented within the context of the INTERSAFE European research project. In sections II and III, a formal description of the problem and the proposed approach is sketched. The experimental results are covered in section IV. Finally, section V provides a summary of the present study and some concluding remarks.

II. PROBLEM STATEMENT

The European research project INTERSAFE is aimed to the development of active safety systems to prevent accidents at road intersections. In order to identify the most relevant scenarios of traffic accidents at intersections, a detailed accident analysis was performed by using statistics of France, Germany and Great Britain. It was found that in France and Germany accidents at intersections plays a central role in traffic accident databases. In addition, three accident scenarios were identified. Namely, accidents caused by collisions with oncoming traffic while turning left (first scenario). Accidents caused by collisions with crossing traffic while turning into straight crossing an intersection (second scenario) and finally traffic light controlled intersection accidents. In particular, red light violation leads often to serious crashes not depending on the type of accident. As an important result, it was shown that most of the accident situations are caused by human errors like misinterpretation or loss of attention.

From the results obtained from traffic accident analysis, it is important to note that a detailed knowledge of the traffic situation is a precondition for an optimal driver-supporting active safety system. To this end, the INTERSAFE test vehicle (hereafter the host vehicle) is equipped with two laser-scanners, one video camera and additional communication systems. The video camera is used to process data about lane markings at the intersection. Furthermore, the laser-scanners collects data of natural landmarks as well as data about other objects and road users. The fused data of the laser-scanner and the video camera together with a detailed map of the intersection are used for localization of the host vehicle within the intersection. Based on this information the advanced safety functions must be designed to correctly interpret the situation to avoid a possible collision. In addition, the driver behaviour (eg. human reaction time) must also be considered when developing the risk assessment algorithm. The ultimate goal is to provide appropriate warnings to the driver to prevent red light or stop sign violations, warnings when turning to prevent collisions with objects in the driving path or from the sides and finally warnings regarding time and distance to the traffic lights. The warnings are presented to the driver by a simple human machine interface (HMI) acoustic and optic based.

However, risk assessment algorithms are not sufficiently known and are still under an early stage of research [10][11]. This fact can be explained in terms of the inherent complexity of the problem. Firstly, the risk assessment algorithm must be able to operate with uncertainty, that is to say, expected imperfections or data errors coming from the measurement system. Secondly, the time-varying nature of the problem makes extremely difficult to properly capture and model the embeddings of information through time. Furthermore, potential risk situations are a combination of multiple factors which are not completely known and are also very difficult to evaluate. In the following subsections the details of our approach are presented, together with some experimental results.

III. PROPOSED SOLUTION

A whole variety of scientific and technical fields are characterized by the fact that patterns of information appear in terms of structured objects. In general, nature provides us with many examples of structured objects, that is to say, objects that can be composed of smaller objects which may be structured too. Possible examples are chemical structures, mathematical expressions or software source code. Moreover, road intersections can be viewed as structured domains, where the structures can be either static or dynamic. Bearing in mind the time-variant nature of the risk and its mutual relation with the interactions and roles of the objects present at road intersections (i.e. vehicles, pedestrians, traffic lights, trees, buildings, etc), we are interested in generating an information encoding procedure as rich as possible to capture the intrinsic relationships between such entities.

Labeled graphs are graphical representations of information that are richer when compared to feature based representations as they permit to express more complex relationships between variables and/or concepts. The nodes of the graph are labeled in the sense that they contain sets of domain variables. Let us denote the set of domain variables associated to any node of a labeled graph as the label space. The variables contained within the label space can be either categorical or numerical. In addition, the presence of an edge between two nodes in a labeled graph indicates that the variables contained in those nodes are related in some way. Therefore, a natural way of encoding the information in a road intersection is by using directed positional acyclic graphs (hereafter DPAGs). More specifically, we encode the domain variables together with the static aspects (i.e. a priori knowledge about the intersection) of road intersections within the label space of the graph and the dynamic aspects of the scene throughout the structure of the graph.

However, the encoding procedure must be designed in conjunction with a computational procedure for the processing of structured information. It is important to note that we are interested in computing a risk value from the available information that the measurement system manages at any given instant time. Recursive neural networks are statistical pattern recognition systems which are able to learn information represented in terms of directed ordered acyclic labeled graphs. They are an extension of recurrent neural networks which are suited for performing supervised and non-supervised learning on data structures with some recent applications [START_REF] Goller | A Connectionist Approach for Learning Search-Control Heuristics for Automated Deduction Systems[END_REF][13] [START_REF] Baldi | The Principled Design of Large-Scale Recursive Neural Network Architectures-DAG-RNNs and the Protein Structure Prediction Problem[END_REF]. In the next subsections, the details of our approach are presented.

A. Information Encoding Procedure

Let us introduce some definitions and notations. A graph is said to be ordered if a total order p is defined on the edges leaving from each vertex. The skeleton of a labeled graph is the data structure obtained by ignoring all the labels, but retaining the topology of the graph. A generic class of graphs skeletons having maximum in-degree i and maximum out-degree o is denoted by the symbol # (i,o) . Once we have specified a label space У and a skeleton class # (i,o) , we may define the space of data structures with labels in У and topology in #. Such a space is denoted by У # .

A super-class of DOAGs is the class of directed positional acyclic graphs (hereafter DPAGs) in which it is assumed that for each vertex v, a bijection P: E → N is defined on the edges leaving from v. DPAGs are a super-class of DOAGs in the sense that every DOAG is also a DPAG, but not viceversa. Bounded DPAGs, or k-DPAGs, are defined by restricting the range of P to the finite set [1,k]  N, for some fixed k. The term positional means that each child has its own position within the set of children of a node. Given a DOAG D and v  vert(D), we denote by ch [v] the set of children of v and by pa [v] the set of parents of v. The indegree of v is the cardinality of the set pa[v] and the outdegree of v is the cardinality of the set ch [v].

The representation and encoding of information procedure can be stated as follows. Firstly, we perform a division of the intersection in zones, as suggested in [START_REF] Fastenmeier | INVENT-FAS/FVM AP[END_REF] but with some substantial differences. We assign to each zone a set of predefined colors from a 6-tuple (yellow, orange, red, cyan, blue and white) that indicate the state of any dynamic object appearing in a scene. Secondly, the state of a dynamic object is defined in terms of its position and direction vector. In addition, directions are referred with respect to the center of the intersection. More specifically, regarding the coloring scheme, we consider the center of the intersection as the reference point to check the directions of dynamic objects. Furthermore, we just consider two generic directions. Namely, between two consecutive sampling points, dynamic objects can either increase either decrease their distance with respect to the center of the intersection. However, if the distance remains equal to zero, (i.e., The vehicle is stopped because of a traffic light) we just consider the previous state to associate a color to the current state. The reason to choose this coloring scheme is based on accident database statistics. Most of the accidents occur within the intersection or nearbound areas to the center of the intersection. Therefore, the encoding scheme cannot ignore this fact: Hot colors (i.e. yellow, orange, red) are assigned to states representing an increased probability of potential danger while cold colors (i.e. cyan, blue) represent just the opposite. Furthermore, colors representing similar concepts are closer from a hamming distance point of view (see table I).

The zone denoted with letter "a" of the intersection is denoted as entering into the intersection zone with yellow as associated color or leaving the intersection zone with blue as associated color depending if the distance of the dynamic object with respect to the center of the intersection is decreasing or increasing with time respectively. Similarly, the zone II is denoted as approaching to the danger zone with orange as associated color or leaving the danger zone with associated color cyan depending on the direction of movement of the dynamic object. Finally, the shaded area of the figure represents the concept of out of the driving area, to denote the portion of the intersection that is out of the road. This area contains for instance, pedestrians, bicycle paths, buildings, trees and so on. On the other hand, the label space was defined as the numerical and categorical information that we attach to the nodes as an array of features. We decompose this vector in three parts: the kinematic space, the state space of the dynamic object and finally the knowledge space. The kinematic space is composed by the set of variables used to characterize the movement of a dynamic object. In particular, we have used as domain variables: position, speed and direction. It is important to remember that at each sampling point the host vehicle recovers a perception of the environment expressed in terms of a set of measurement variables. The state space of the dynamic object is the set of states used to represent the behavior of dynamic objects (vehicles, pedestrians, bicycles, etc). In addition, the state of dynamic objects is represented by a 6-tuple of colors (see table I). Colors representing similar concepts are closer from a hamming distance point of view. Finally, the knowledge space represents the restrictions or a priori knowledge that can be associated to each graph node. In our experiments we just consider three knowledge dimensions: Speed limit violations, driving way violations and potential traffic light violations. These dimensions are represented by means of three binary variables (see table II).

To give an example of the construction process, consider the graph depicted in Figure 2. The root node of the graph (denoted by the symbol #) will always correspond to the host vehicle. In addition, the maximum out-degree of the graphs is determined by the sensor characteristics, although from a practical point of view we can fix in advance this quantity to reduce the complexity of the graphs.

The position of the child indicates the type of object detected by the sensors of the host vehicle. In this line, a convention is defined to represent the host vehicle. Specifically, in our experiments the right-most child of any graph node is always assigned to represent the host vehicle (see figure 2). In this example we assume that the maximum out-degree of the graphs is three. Namely each node of the graph can have a maximum number of three children where each child corresponds to a dynamic object detected by the host vehicle with its sensors. The position of the child indicates the type of object detected by the host vehicle. In addition, the order in the graph is determined by the cardinality of the number attached to each node, which is related to the temporal sequence of events. Attached to each node there is also an informative label indicating the type of dynamic object (ie., vehicles, pedestrians, bicycles etc). The letters a,b,c denote the positions of any child with respect to its parents.

It is easy to deduce that the above-mentioned encoding procedure is invariant with respect to rotations and/or translations and naturally incorporate both symbolic and numerical information. Furthermore, the proposed encoding procedure does not depend on specific traffic regulation laws. For instance, driving ways may differ between the countries.

B. Recursive Neural Networks

Recursive Neural Networks are computational models capable of performing mappings from a set of labeled graphs to a set of real vectors. Specifically, they are based on the following recursive state space representation:

Here v is a generic node identifier. The state vector a(v) associated with node v is a function of the ordered state vector associated with its children a(ch [v]) and the input vector I(v) that encodes the set of attributes attached to node v as a label.

The basic idea is to use recursive neurons to encode the structures. Namely, to perform the state transition function f and the representations obtained are then used to approximate the output function g by a standard feedforward network, like a multilayer perceptron. The standard algorithm for training recursive neural networks is the Back-Propagation Through the Structure algorithm [START_REF] Goller | Learning Task-Dependent Distributed Structure-Representations by Backpropagation Through Structure[END_REF] (hereafter BPTS). However, BPTS suffers the problems of slow convergence associated to any gradient descent procedure. In this section we propose a quasi-newton learning algorithm hereafter Quasi-Newton Through the Structure (QNTS). Let us start by defining an error measure E(.) that is defined in the parameter space Ω f x Ω g which are represented by the model parameters w f , w g (parameters of the state transition function f and the output function g respectively). In addition, we assume a training set of data structures D = {(U,Y), U  U # , Y У # }. The error function E: Ω f x Ω g → R formulated for the inductive learning task, accumulates the error contributions of each input-output pair in the pattern set of structures D. Borrowing the notation of [17] we can represent the standard squared error function as follows:

In the above equation the function t(.) is introduced to access the target label for a given node of the input graph. In order to devise a quasi-newton algorithm we need to compute the first-order gradient information to compute a sequence of matrices representing approximations of the inverse Hessian (second order information). In addition, to reduce the effective complexity of the state transition network soft weight sharing technique is used. Namely, model parameters are shared among the nodes of the graphs and the gradient of a structural pattern U is computed by summing up the individual node contributions. Let us denote by w f (v) and w g (v) the parameter vectors at node v  U. Thus, we can express the error gradient of one graph U with respect to the parameters w f and w g for v  U. The parameters w g (v) do only influence the error contribution E(v) of the node v. We get:

Where y i (v) is the i-th component of the model output computed for node v, and J w g is the Jacobian matrix of the output function g with respect to the parameters w g which has to be evaluated at location a(v) and δ g is given by δ g (v) = y(v) -t(v). The error contribution of a node z is influenced by all parameters w f (v), v  U where there is a path in the input graph leading from z to nodes v. We have:

Where a i (v) is the i-th component of the state computed for node v, is the Jacobian matrix of the state transition function f with respect to the parameters w f which is evaluated at the states a(ch [v]) known for the children of node v and its input label I(v). The term δ i f (v) is determined as follows:

The above equation measures the effect of the state a(v) on the error E(v). The first term expresses the direct influence on E(v) while the second one collects the indirect effects that are propagated through the parents of node v. Equation 4 can be expressed in matrix form as follows:

Where J x g denotes the Jacobian matrix of the output function g with respect to its input arguments J x(r) f stands for the transposed Jacobian of the state transition function f to respect to those input arguments that belong to the corresponding child, for instance r = ord(v,z) if the node v is the r-th child of node z. From the considerations stated above, an algorithmic specification can be deduced. The pseudo-code of the quasi-newton algorithm is shown in figure 3. The algorithm works in batch mode. Namely, the gradients associated to the whole training set are computed before making an update on the parameter space of the neural network. Functions, S-GRADIENTS and P-GRADIENTS are used to compute the gradients associated to the structural patterns. The pseudo-code of these functions is presented in the appendix section. The procedure for computing the successive approximations to the inverse of the Hessian is BFGS [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. In addition, the line search procedure used is backtracking [START_REF] Dennis | Numerical Methods for Unconstrained Optimization and Nonlinear Equations[END_REF].

IV. EXPERIMENTAL RESULTS

This section describes the experimental settings used to test the ideas presented so far. The goal pursued is just to show the potential of the approach throughout standard scenarios constructed by using simulated data.

Firstly, in our experiments, we consider a standard crosslike intersection consisting in a square of 100m 2 , two driving ways, each way having two lanes of 3 meters each. We assume a speed limit of 80km/h when approaching to the intersection. The system coordinates, is placed at the center of the intersection. For the sake of simplicity we assume that the simulated scenes only contain two dynamic objects (host and remote vehicle). Therefore, the structural patterns belong to the skeleton class # (1,2) and are to be mapped by the recursive neural network into a continuous variable in the interval [0,1] indicating the level of risk. Similarly, from the accident scenarios explained in section II, we just consider the left turn across path and the traffic light scenario. In addition, in all the simulations the system is sampled at 200ms. Moreover, with the aim of generating a realistic set of situations, a collision detection module was developed. Specifically, it is based on a trajectory module, a stochastic sampler and a collision detector. Trajectories are generated by using the following procedure: Firstly, a set of checkpoints in the kinematic space of the vehicles are generated which roughly describe the trajectories to be followed by the dynamic objects. For example, if the host vehicle is supposed to follow the lane and cross the intersection, some logical check-points would be: center point of the lane before the intersection, center point of the lane after the intersection and some exit point. Moreover, there is an error or uncertainty associated to each dimension of the kinematic space. Afterwards, a set of trajectories, constructed by using Bézier polynoms, are generated by sampling the stochastic check-points. In addition, speed, position and direction are modeled by using a gamma, triangular and normal probability distribution functions respectively. From the sampled trajectories, structural patterns are constructed by following the temporal sequence of the trajectories and shifting in time pairs of trajectories corresponding to the host and the remote vehicle. Thus, a whole variety of situations are simulated. In addition, visibility restrictions (i.e. sensors area coverage) are taken into account when generating the structural patterns. Moreover, the maximum depth of the tree-like graphs is limited by a risk window of 1.5s that takes into account the human reaction time.

Following the above-mentioned procedure a pattern set of 4000 structural patterns was generated. In addition, as stated in section III, the risk assessment problem is formulated as an inductive learning task. Therefore, two components are needed. Firstly, a teacher function is needed to rate the structural patterns. Specifically, the teacher provides a desired response or target for every structural pattern received from the dynamical system (the road intersection). In addition, the teacher function is supposed to be noisy as the quality of its associations will depend on the amount of knowledge encoded by the function. At this point, it is important to note that the expected goal is to produce a model that minimize the structural risk, outperforming at the same time the built-in knowledge of the teacher function, something that is not possible, if we think in a real-world industrial application, with simulated data. In our simulations, the teacher function is a weighted function that is mainly composed of two terms. The first term checks violations of the knowledge space while the second detects possible collisions of the host vehicle with the remote vehicle. Therefore, given a structural pattern the teacher function computes a value belonging to the interval [0,1] indicating the level of risk associated to the scene.

Secondly, a learning machine or algorithm is needed to learn the input-output mappings. As a learning machine recursive neural networks are used and trained with the algorithm proposed in section III. More specifically, from the pattern set, 2000 patterns are used for training and the other 2000 for validation purposes where 1138 of them corresponding to collision situations (target value equal to 1). Table III depicts the simulation results, two architectures were tested, the first having 23 state neurons, 160 hidden neurons and 1 neuron for the output layer. The second with 20 state neurons, 150 hidden neurons and 1 output neuron respectively. The output of the network and the targets associated to each structural pattern were discretized to compute the generalization capability of the networks using a threshold value of 0.5. Specifically, network outputs and targets bigger or equal than 0.5 were assigned to 1 and 0 respectively to indicate risk or not risk at all. In both simulations the algorithm was run 500 epochs and the generalization capability was tested at this moment. The results show that the model was able to recognize completely new dangerous situations. However, it must be noted that these results are just an indication of the potential of the ideas sketched throughout this paper. A strict validation of the proposed approach it is only possible with real data.

V. CONCLUSIONS AND FUTURE WORK

In this paper we have investigated the application of recursive neural networks to compute risk functions. We have presented a formal description of the problem in terms of its application context. Specifically, within the Intelligent Transportation Systems research field.

The main contribution of this paper is reflected by the fact of considering the risk as a geometrical object with a specific structure that can be learnt by an appropriate computational model. More specifically, we have shown that the geometry of the risk is determined by taking into account the combined actions and roles of the objects present at road intersections. To this end, a novel information encoding procedure based on directed ordered acyclic graphs was proposed to extract the intrinsic relations between such objects. The proposed encoding procedure permitted us to combine disparate source of information in a compact structure that allowed expressing complex relations between information units that can vary in size. Afterwards, the risk assessment at road intersections was reformulated in terms of an inductive learning task. At this point, recursive neural networks were introduced as highly non-linear adaptive models that are able to learn structured data even if such data was noisy or incomplete. The main drawback of these models is a computationally expensive training phase together with a laborious pattern generation procedure. However, the main motivation of using neural networks is reflected by the fact of being models with the so-called recognition without definition property that enables systems to generalize. Specifically, the ability to recognize multitudes of unforeseen complex patterns without any ability to define them. Although further research must be carried out, the preliminary results have shown that the resulting model is able to recognize new dangerous situations given that risk information is implicitly encoded within the structural patterns that were learnt by the neural network during the training phase.

Our current work is focused on implementing the proposed methodology in a vehicle equipped with the INTERSAFE technology to validate the ideas presented throughout this paper in a real-time scenario.

APPENDIX

The function S-GRADIENTS depicted in figure 4 expects a pair (U,Y) of input and target graph and returns the firstorder gradients with respect to the model parameters w g and w f . It is important to note that a topological ordering is defined for the structures. In addition, the function P-GRADIENTS it is just a helper function that simply collects the gradients contributions associated to each structural pattern in the training set.

  Fig. 1 Generic intersection subdivided into symmetrically equivalent zones.

Fig. 3 .

 3 Fig. 3. Pseudo-code of the Quasi-Newton Through the Structure Algorithm