Parsing in second order ACGs
Clovis Eberhart

Contents
1 Abstract Categorial Grammars
1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Other features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
5
5

2 Parsing in ACGs
2.1 Reduction to Datalog . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Other parsing problems . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
7
8
9

3 Applications
3.1 Expressive power of second order ACGs . . . . . . . . . . . . . . . . . . .
3.2 Tree-adjoining grammars . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Accurate automatic translation . . . . . . . . . . . . . . . . . . . . . . .

10
10
11
12

1

Introduction
Natural Language Processing (NLP) is a very wide field of study that has to do withnatural language, how it can be understood or generated, how information can be dugfrom a text in a book, how grammatical structures turn into concrete sentences...
In NLP, there exists many formalisms to describe grammatical structures and how
these structures are transformed into actual sentences and a meaning can be infered fromthem.
In 2001, Philippe de Groote [1] introduced a new formalism called Abstract Categorial
Grammars that aims at unifying most of the other formalisms under a general and very
simple formalism to describe grammatical structures and how they are transformed into
syntactical structures.
The problem that we face here is the problem of parsing in second-order (a certain classof) Abstract Categorial Grammars and implementation of the corresponding algorithm.
Parsing is the problem of having a concrete sentence and trying to find the grammaticalstructure behind it.
This problem has been solved by Makoto Kanazawa [3], and it reduces the problemof parsing in a second-order ACG to the problem of solving a query in Datalog, which is
decidable. What I did was implement this reduction to solve this problem of parsing.
We will first inroduce the notion of Abstract Categorial Grammars and give an example, then study in detail parsing in second-order Abstract Categorial Grammars andhow it is reduced to Datalog solving, and finally we will see the limits of this algorithm
and a possible application.

2

Chapter 1
Abstract Categorial Grammars
1.1

Definition

Abstract Categorial Grammars (ACGs) is a formalism that describes the interface between grammatical structures and syntax in natural language. It is based on linear logic
and the associated linear λ-calculus.
ACGs are based on linear implicative types on a set of atomic types A, defined by:
I(A) ::= A I(A) ( I(A)The rules to deduce a formula in linear logic are:

A`A

(Ax)

Γ, A ` B
Γ`A(B

(Abs)

Γ`A ∆`A(BΓ, ∆ ` B(App)

Note that there is no weakening rule, i.e. Γ ` A does not imply Γ, ∆ ` A, and thatthe sign ( denotes linear implication. This can be seen as resources-wary logics as every
hypothesis has to be used once and only once.
A higher-order signature Σ is a triple (A, C, τ ) where A is a finite set of atomic types,
C is a finite set of constants and τ is a mapping from C to I(A).
The intuition behind the definition of a higher order signature is that, on a grammatical point of view, constants in C correspond to basic grammatical constructions andtheir type τ (C) corresponds to how they interact. We want to describe the interaction
between words by use of linear logic, a sentence is well-structured when one is able todeduce S (sentence) by use of linear logic on the types of the words in the sentence. Hereis a concrete example of a higher order signature:
We have a higher-order signature Σ1 = (A1 , C1 , τ1 ), where A1 = {N, N P, S}, C1 ={Jean, mange, une, pomme} and τ1 = {Jean 7→ N P, mange 7→ N P ( N P ( S, une 7→
N ( N P, pomme 7→ N }. N stands for noun, N P for noun phrase and S for sentence.
Jean is a constant that correspond to the French name ’Jean’, which is indeed a nounphrase, mange is a constant that corresponds to the French verb form ’mange’, which canbe seen as a function that takes two noun phrases (its subject and object) and returns a3

sentence, hence the type N P ( S, une represents ’une’, which can be seen as a functionthat takes a noun and returns a noun phrase, and pomme represents ’pomme’, which isa noun.
If X is an infinite set of λ-variables, the set Λ(Σ) of linear λ-terms built on Σ =(A, C, τ ) is defined by:• x ∈ X, then x ∈ Λ(Σ)• if c ∈ C, then c ∈ Λ(Σ)• if x ∈ X occurs free in t ∈ Λ(Σ) exactly once, then λx · t ∈ Λ(Σ)• if t, u ∈ Λ(Σ) and free variables of t and u are disjoint, then tu ∈ Λ(Σ)
The rules to type linear λ-terms built on Σ are:c∈C(cons)`Σ c : τ (c)Γ, x : α `Σ t : β(abs)Γ `Σ λx · t : α ( β

x∈X
(var)
x : α `Σ x : αΓ `Σ t : α ( β ∆ `Σ u : α(app)Γ, ∆ `Σ tu : β

A lexicon L from a signature Σ1 = (A1 , C1 , τ1 ) to a signature Σ2 = (A2 , C2 , τ2 ) is a
couple (F, G) where:• F is a function from A1 to I(A2 )• G is a function from C1 to Λ(Σ2 )• F and G are compatible with the typing relation, i.e.:∀c ∈ C1 , `Σ2 G(c) : F̂ (τ1 (c)), where F̂ is the only homomorphism that extends F .
From here on, L will also denote F and G in contexts where the meaning is clear.
An ACG a quadruple G = (Σ1 , Σ2 , L, s) where L is a lexicon from Σ1 to Σ2 and s ∈ Σ1
is a distinguished type. Σ1 is called the abstract vocabulary and represents the abstract
sturcture of the grammar, Σ2 is called the object vocabulary and represents the syntax ofa language. An ACG produces two languages :• the abstract language A(G) = {t ∈ Λ(Σ1 )| `Σ1 t : s} that represents all valid
grammatical strucutures of a language• the object language O(G) = L(A(G)) that represents the concrete realisation ofthese abstract structures

4

1.2

ExampleHere is a concrete example of an ACG for a very tiny part of French grammar to show
how to check that a sentence is valid (meaninig that it’s part of the object language):
Σ1 is defined as in the example above, and Σ2 = (A2 , C2 , τ2 ) is defined by A2 ={string}, C2 = {+, Jean, mange, une, pomme} and τ2 = {+ 7→ string ( string (string, Jean 7→ string, mange 7→ string, une 7→ string, pomme 7→ string} (where +represents the concatenation operator, and will be used with an infix notation for clarity). We define L = {F = {N P 7→ string, N 7→ string, S 7→ string}, G = {Jean 7→
Jean, mange 7→ λx, y · x + mange + y, une 7→ λx · une + x, pomme 7→ pomme}}. The
distinguished type is S.
The linear λ-term mange Jean (une pomme) is a valid grammatical structure, sincemange has type N P ( N P ( S, Jean has type N P , hence `Σ1 mange Jean : N P (S, une has type N ( N P , pomme has type N , hence `Σ1 une pomme : N P and`Σ1 mange Jean (une pomme) : S. The concrete structure corresponding to it isL(mange Jean (une pomme)) = (λx, y · x + mange + y) Jean ((λx · une + x) pomme) →∗βJean + mange + une + pomme. Therefore, Jean + mange + une + pomme is a valid sentencein French.
On the other hand, the following sentences are not valid in French:• une + Jean + pomme + mange, because there is no linear λ-term t such that L(t) →∗β
une + Jean + pomme + mange• mange, because any λ-term t such that L(t) →∗β mange is of type N P ( N P ( S
Although the natural idea for the object signature is one that describes the realisationof a grammatical structure in a given language, it can also be the realisation of thatgrammatical structure as a logical proposition that describes the meaning of the sentence
associated to it. It is a very powerful feature of ACGs to be able to treat a grammaticalstructure’s syntax and its semantics the exact same way. Therefore, computing themeaning of a grammatical structure is nearly as easy as computing the syntactic struxture
that corresponds to it. Here is an example of a second ACG that correspond to theprevious one, but whose object language is the meaning of the grammatical structure (Ido not pretend I understand the semantics, I just give an example to show this is handled
the very same way):Σ1 is as above, Σ2 = (A2 , C2 , τ2 ), with A2 = {e, t}, C2 = {John, eat, apple} andτ2 = {John 7→ e, eat 7→ e ( e ( t, apple 7→ e ( t}. We define L = {F = {N P 7→ (e (t) ( t, N 7→ e ( t, S 7→ t}, G = {Jean 7→ λP · P John, mange 7→ λP, Q · Q (λy · P (λx ·eat x y)), une 7→ λP, Q · ∃x · P x ∧ Q x, pomme 7→ λx · apple x}}.
Then we have L(mange Jean (une pomme)) = (λP, Q · Q (λy · P (λx · eat x y)))(λP ·P John)((λP, Q · ∃x · P x ∧ Q x)(λx · apple x)) →∗ ∃x · apple x ∧ eat John x

1.3

Other features

A pleasant and useful feature of ACGs is that they form a category, with signatures asobjects and lexica as arrows. This provides, for example, a way to compose ACGs, which
5can be useful in order to restrict the abstract language of an ACG. Indeed, if too many
sentences are valid in an ACG G12 = (Σ1 , Σ2 , L12 , s1 ), it may be useful to find an ACG
G01 = (Σ0 , Σ1 , L01 , s0 ) to restrict the abstract (and therefore object) language of G12 , andto study G02 = (Σ0 , Σ2 , L12 ◦ L01 , s0 ).
An important notion in the ACG theory is the notion of order of an ACG, which
describes the expressive power of a class of ACGs. It is particularily important to us, as
we will only study second-order ACGs. The order of a linear inductive type is defined byinduction by:• ord(A) = 1 if A is an atomic type• ord(A ( B) = max{ord(A) + 1, ord(B)}The order of an ACG is defined by ord(G) = max{ord(τ (c)) | c ∈ C1 }.
First order ACGs are pretty useless, as their abstract languages is defined by the
portion of their abstract vocabulary with type s.
Second order ACGs have a much greater expressive power and can be used for some
simple grammars. One may define transitive verbs with type N P ( N P ( S, where
the first N P is the subject and the second one is the object. For example, loves would
have this type and be associated with the λ-term λx, y · x + aime + y in French grammar.
L(loves John M ary) would then reduce to Jean + aime + Marie.
Third order ACGs are really useful, as they can be used to define relative clauses.
who, for example would have type (N P ( S) ( N P ( N P and be associated withthe λ-term λx, y · x (y + qui) in French grammar. The following example aims at giving
some intuition: L(is John (who (a man)(λx · loves x M ary))) would then reduce toJean + est + un + homme + qui + aime + Marie.

6

Chapter 2
Parsing in ACGs
2.1

Reduction to Datalog

The general problem we face here is the problem of parsing in an ACG. Going fromthe abstract stucture to the object structure (applicative paradigm) is very easy, as weonly need to apply a lexicon and β-normalize the result. The problem of parsing is theother way around: we have a term u built on the object signature, and we would like toknow whether there exists a term t built on the abstract signature such that L(t) →∗β u(deductive paradigm). This corresponds to trying to inverse a lexicon. This, however, is
not easy in the general case, it is not even known whether it is decidable.
In our case, we only consider second-order ACGs, and the problem becomes decidable,
as an algorithm has been found by Makoto Kanazawa [4]. It reduces a problem of parsing
in second-order ACGs to a problem of trying to infer a fact with Datalog, which is
decidable with a good complexity in some cases.
Datalog derives facts in first-order logic through the use of Horn clauses. It uses
a Datalog program and an extensive database. The extensive database is a set of facts
that are true. The Datalog program is a set of rules (Horn clauses) used to derive newfacts. Such a rule is written p(x1 , ..., xn ) :− p1 (x1,1 , ..., x1,n1 ), ..., pm (xm,1 , ..., xm,nm ), whichmeans that if p1 (x1,1 , ..., x1,n1 ), ..., pm (xm,1 , ..., xm,nm ) are true, then p(x1 , ..., xn ) is also
true. There is a Horn clause that corresponds to this statement:p(x1 , ..., xn ) ∨ ¬p1 (x1,1 , ..., x1,n1 ) ∨ ... ∨ ¬pm (xm,1 , ..., xm,nm )If p(x1 , ..., xn ) is derivable for a Datalog program P and an database D, then we write
P ∪ D ` p(x1 , ..., xn ). The set of predicates that are at the head of a rule is called theintensional database.
The sequence of constants in a λ-term M ∈ Λ(Σ) when it’s read from left to right−−→is noted Con(M ). The sequence of its free variables when it’s read from left to right is−−→−−→c[x1 , ..., xn ] thenoted F V (M ). If M is close and Con(M ) = (c1 , ..., cn ), then we note M
λ-term with M where ci has been replaced by xi . A typing of M is a derivable judgmentΓ `Σ M : α. M is said to be in η-long β-normal form relative to Γ ⇒ α if it’s β-normal
and there is a deduction of Γ `Σ M : α that is η-long.
To a second-order ACG G = (Σ, Σ0 , L, S), we associate a Datalog program program(G),whose intensional database is A and extensional database is C 0 . We assume that for every7c ∈ C, L(c) is in η-long β-normal form relative to L(τ (c)). The arity of p ∈ A is thenumber of atomic type occurences in L(p). The arity of d ∈ C 0 is the number of atomic
type occurences in τ 0 (d). Each constant c ∈ C gives birth to a single rule ρc as follows:−−→
if τ (c) = p1 → ... → pn → p0 , Con(L(c)) = (d1 , ..., dm ) and y1 : β1 , ..., ym : βm `d 1 , ..., ym ] : α1 → ... → αn → α0 is a principal typing of L(c)[yd 1 , ..., ym ] then:L(c)[yρc = p0 (α0 ) :− p1 (α1 ), ..., pn (αn ), d1 (β1 ), ..., dm (βm ) where α is the sequence of atomic
types in α when read from left to right. These atomic types are considered here as Datalog
variables.
The Datalog program associated to G is program(G) = {ρc | c ∈ C}.
−−→
Let p ∈ A and M ∈ Λ(Σ0 ) be in η-long β-normal form relative to L(p). If Con(M ) =c[y1 , ..., ym ] : α is a principal typing of Mc[y1 , ..., ym ],(d1 , ..., dm ) and y1 : β1 , ..., ym : βm ` Mthen we define:
database(M ) = {di (βi ) | 1 6 i 6 m}
queryp (M ) = {p(α)}
Theorem 1 (Kanzawa) Let G = (Σ, Σ0 , L, S) be a second-order ACG and p ∈ A. Suppose that N ∈ Λ(Σ0 ) is in eta-long beta-normal form relative to L(p). Then the following
are equivalent:• there is P ∈ Λ(Σ) such that `Σ P : p and L(P ) →∗β N• program(G) ∪ database(N ) ` queryp (N )2.2

Implementation

The work I had to do during this stage was to implement the reduction of second-order
ACGs to Datalog programs in OCaml. At the beginning of my stage, the prototype for
ACGs already included modules to manage λ-terms, higher-order signatures and lexica,
modules to manage Datalog programs and signatures, and a Datalog solver. The modules
I had to implement were a module for type inference and a module to transform an ACG
into a Datalog program.
The difficult parts of this work were to understand the notion of ACGs, to understandthe global structure of the code and how all the modules interacted, then to understandan unpublished article by Kanazawa [3] that explained the reduction in a very detailed
way and then difficulties about writing code.
In the reduction, the only really difficult part to implement was the type inference
algorithm. Hopefully, I had already written one, so I knew how to do it, though thestructure of λ-terms was a little complicated (use of de Bruijn indexes).
Another difficult task, though it is not directly related to the fact that I manipulatedACGs, is that I had to change a data structure (how λ-terms were described in the
ACG modules) to another structure (how Datalog programs are handled) without having
written any of these structures.
Although I would have liked to parse a French sentence to have its grammaticalstructure and then use this structure to infer the sentence’s semantics with another ACG,
I could not. The reason is that the Datalog solver did not return enough information8

to recontruct the abstract structure corresponding to the sentence (the solver awnsered
whether the fact was derivable but did not give its derivation).
I would also have liked to try to parse a logical proposition to find the grammaticalstructure behind it and then compute the corresponding sentence in French. It was
impossible for the same reason as above.
I did obtain some results though. Consider the ACG G = (Σ1 , Σ2 , L, S), where Σ1 ={{S}, {R1 , R2 }, {R1 7→ S, R2 7→ S ( S}}, Σ2 = {{o}, {a, b}, {a 7→ o ( o, b 7→ o ( o}}and L = {{S 7→ o ( o}, {R1 7→ λx · x, R2 7→ λx · a + x + b}} (it is the reduction of
S → aSb |  to a second-order ACG and o ( o represents the string type). I applied the
reduction to it and obtained the Datalog program:c.S(i, i).
c.S(i, j) :− t.+(k, l, m, n, i, j), t.a(k, l), t.+(o, p, q, r, m, n), c.S(o, p), t.b(q, r).
which is the reduction of this ACG. The databases and queries I got when applying my
implementation of the reduction also corresponded to what the reduction should give.

2.3

Other parsing problems

In the general case, it is not known whether parsing is decidable in an ACG. Sylvain
Salvati [5] showed that it is equivalent to decidability of proof research in MELL.
In some other cases, parsing in an ACG remains decidable. For example, if the ACG
is lexicalised (the image of every abstract constant through the lexicon contains an object
constant), then parsing is decidable. There exists an algorithm, found by Sylvain Salvati[5], that solves the problem. Its complexity, however, is unknown.
One thing that could be very nice would be to have a parser for ACGs of boundorder (third order would already be pretty good). One may think of trying to adapt thetechnique used for second order ACGs for third order or greater ones. Yet, the reductionuses the simple form of skeletons of second order types, which is not the case anymore inthird or greater order. Therefore, it seems very unlikely that this technique would adapt
to third or greater order ACGs.

9

Chapter 3
Applications
3.1

Expressive power of second order ACGs

To understand the extent of possible applications of the parser of second order ACGs, weneed to know the expressive power of second order ACGs.
The general expressive power of ACGs is unkown. Yet, a number of grammars canbe encoded in ACG formalism, thus giving a ’lower bound’ of ACGs’ expressive power.
Here are some grammars that second-order ACGs can encode, the encodings are detailedin [2].
• context-free grammars, whose rules have the form X → w where X is a nonterminal symbol and w is a word made of terminal and non terminal symbols. Sucha rule can be written in another way, as in the following example : S → aBBS canbe rewritten S(aXY Z) :− B(X), B(Y ), S(Z). The idea here is that you deduce
S(aXY Z) from B(X), B(Y ), S(Z) (if you can produce X with B, Y with B andZ with S, then you can produce aXY Z with S), a word w is in the language when
one can deduce S(w). The first writing is a top-down view, the second one is abottom-up view.
• multiple context-free grammars, whose rules have the formX(u1 , ..., un ) :− X1 (u1,1 , ..., u1,n1 ), ..., Xm (um,1 , ..., um,nm ). These grammars are more
powerful than context-free grammars, as the grammar made of the following rules:
S(x1 y1 x2 y2 ) :− A(x1 , x2 ), B(y1 , y2 ) A(, ) A(ax1 , cx2 ) :− A(x1 , x2 ) B(, )B(by1 , dy2 ) :− B(y1 , y2 ) generates the language an bm cn dm .
• tree adjoining grammars is a formalism that has been studied a lot in NLP because
it can parse natural language well with two simple operations. This formalism isfurther discussed in the next section.
• ACGs can also encode linear context-free tree grammars. Here is an example ofsuch a grammar : S(Y (e, e)) :− A(Y ) A(aY (b, b)) :− A(Y ) A(f (, ))genereates the language an f (bn e, bn e) (where parentheses have not been marked
when there is a single child and  is a hole).
• multiple linear context-free grammars are to linear context-free tree grammars what
multiple context-free grammars are to context-free grammars. Here is an example
10

of such a grammar : S(f (X1 , X2 )) :− A(X1 , X2 ) A(g(a, X1 , b), g(c, X2 , d)) :−A(X1 , X2 ) A(e, e) generates a language whose leaf language is an ebn cn edn .
We have seen that second-order ACGs can encode a lot of different and powerfulformalisms, but, in terms of strings, they cannot encode more than this, as states Salvati’s
theorem.
Theorem 2 (Salvati) The expressive power of second-order string ACGs is the sameas that of multiple context-free grammars.

3.2

Tree-adjoining grammars

Tree-adjoining grammars have been widely studied and used in NLP as they are conjectured to be able to produce natural language while being easily parsable in the generalcase.
A tree-adjoining grammar is defined by a set of terminal symbols, a set of non-terminal
symbols, a set of initial trees and a set of auxiliary trees. The union of initial trees andauxiliary trees is called elementary trees. They must verify the following:• the leaves of initial trees are terminal symbols or non-terminal symbols, which arethen called substitution nodes,• the leaves of auxiliary trees are terminal symbols or non-terminal symbols, which
are then substitution nodes, except for a single non-terminal leaf, that has the same
symbol as the root and is called the foot node
There are two operations possible with tree-adojoining grammars. The set of trees
derived by these operations is called derived trees.
• Substitution: this operation is very easy to understand. It replaces a substitution
node of a tree α by an initial or derived tree β if the substitution node and β’s root
node share the same symbol.
• Adjunction: this operation is a little trickier. The intution behind this operation istrying to insert a tree into another tree. To adjoin a tree β to a tree γ at node n,
the sub-tree δ of γ with root n is removed from γ and substituted to β’s foot node,
the result is then substituted in γ at node n.
The following figures show examples of substitution and adjunction.

11

In these pictures, the usual TAG notations are used, that is that substitution nodes
are noted with a downwards arrow and foot nodes are noted with a star.

3.3

Accurate automatic translation

As we have seen, a very powerful aspect of ACGs is that this formalism uses the same
tools to generate sentences in a given language and a logical proposition to describe themeaning of a grammatical structure. This can be used to build an accurate automatictranslator. The idea is that instead of trying to translate a sentence, the automatictranslator is going to ’translate’ the sentence into a logical proposition that will then be’translated’ into another language. More precisely, it will transduce (parse in an ACG an
apply in a second ACG) the sentence in a logical proposition, and then transduce this
proposition into a sentance again.
For example, to translate from French to German the sentence Jean+dort, the sentence
is going to be parsed in an ACG that corresponds to French language, which will return
dort Jean, this is then transformed in a second ACG to find its meaning, which will
return sleep John, this is then parsed in a third ACG that is symetrical to the second
one, but in German, it will return schläf t Johan, which will ultimately be tranformed bya fourth ACG (symetrical to the first one, but in Greman), which will give Johan+schläft.

12

Conclusion
I think the part I wrote in the ACG prototype was a fundamental one, even though
all basic features were already written. Actually, without parsing, ACGs have no realinterest with respect to NLP, as it is what is most important when one wants to dig
information from text. The next step would be to improve the Datalog solver, so that it
returns the derivation of the query, so that the grammatical structure may be constructedfrom the object realisation through parsing. That would already allow transduction andtherefore automatic translation. Another possible improvement would be to implement
a parser for the lexicalized case as an algorithm exists and it would allow to parse more
complex sentences, with relative clauses and the likes.
This stage, although a little short, made me experience a lot of things that werecompletely new to me. First of all, even though I had been programming in CamlLight andOCaml for four years, I had never used modules when writing code, which is impossible
when projects get bigger. I also learned to use Emacs in a very basic way, allowing me towrite and compile code much faster than before. I also learned to use Subversion, readand modify Makefiles and configuration files, among other things.
I would like to thank all the people I met when I was in Nancy, as they were all
nice to me. Of course, Sylvain Pogodalla, who directed me for seven weeks and wasalways highly responsive even when he did not have much time. All the researchers, PhD
students, engineers, interns and the assistant at team Calligramme, and the people I met
in LORIA in general, who were always nice and lively, who gave me good pieces of advice
and spent time with me.

13

Bibliography[1] Philippe de Groote. Towards abstract categorial grammars. In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European
Chapter, Proceedings of the Conference, pages 148–155, 2001.
[2] Philippe de Groote and Sylvain Pogodalla. On the expressive power of abstract categorial grammars: Representing context-free formalisms. Journal of Logic, Language
and Information, 13(4):421–438, 2004.
[3] Makoto Kanazawa. Second-order acgs as datalog programs. unpublished, August 2006.
[4] Makoto Kanazawa. Parsing and generation as datalog queries. In Association for
Computational Linguistics, 45th Annual Meeting, Proceedings of the Conference,
pages 176–183, 2007.
[5] Sylvain Salvati. Problemes de Filtrage et Problemes d’Analyse pour les Grammaires
Categorielles Abstraites. PhD thesis, Institut National Polythechnique de Lorraine,
2005.

14