La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

G
orteur
Mem
Examinateur
Examinateur
cob
juin
Ja
tteux
e
aerr
Petitot
Examinateur
N
souten

t
drdre
:
:
t
1289
orteur
TH
Galligo

R
ESE
eren
pr


le
esen
dev
t
commission

du
ee
M


a
Giusti
LNIVERSIT
Lazard

Carr
E
Examinateur
DES
F
SCIENCES
Diop
ET
ouche
TECHNOLOGIES
M
DE
tiell
LILLE
Th
p
ese
our
ue
obtenir
27
le
1994
titre
an
de
la
DOCTEUR
dxamen
en
bres
INF
jury
ORMA
MM
TIQUE
La
par
Pr
F
esiden
ran
M
cois
Rapp
Boulier
D

Rapp
Etude
G
et

implan
o
tation
A
de
Examinateur
quelques
Ollivier
algorithmes
S
en
Examinateur
alg
Bk

Examinateur
ebre
di

Laboratoire d’Informatique
Fondamentale de LilleL IFL
tel-00137866, version 1 - 22 Mar 2007Ce

p
ts

L
sym

on
equip
ees
e
lcole
de
eor
Calcul
dncouragemen
F
Mic
ormel
fait
forme
la
un
e
group
VI
e
hes
actif
En
au
qui
sein
p
du
de
LIFL
reviennen
Ce
te
dynamisme
Sa
est
Latteux
bien

s
etail
^
rise
ur
emoire
d
a
^
e
u
v


a
remarques
la
ran
p

ersonnalit
ee

quls
e
Marc
de
un
ses
aid
mem
qui
bres
une
mais
est
aussi
a
je
tan
p
dans
ense
Je

d
a
ce
ses
me
th
souci

emonstrations
emes
de
de
ji
rec
ediger
herc
orteurs
he
Daniel
qui
e
plongen
cois
t
hes
leurs
co
racines
Directeur
dans
^
trois
lcole
disciplines
doit
:
mn
informatique
Daniel
automatique
our
et
mn
math
de

la
ematiques

Cette
aussi
pluridisciplinarit


men
e
la
rend
eu
les
e
th
t

a
eses
ann
de
es
calcul
p
formel
onne
diiles
P
aux
ure

LIFL
etudian
ec
ts
sp
en
emen
informatique

qui
jury
les
t
ab
Mic
orden
au
t
oir
et

qui
de
n
Cst
son
elan
t
et
pas
d
toujours
d
pr
os

ses
epar
Ma

dnformatique
es
y
mais
r
elle
m
les
Les
rend
cette
du
son
m
Professeur
^
ersit
eme
a
coup
F
tr
Charg

Rec
es

in
olytec
t
orteur

Marc
eressan
Rec
tes
et
parce
de
que

li
olytec

v
ees
eaucoup

t
a
fait
des
je
probl
et

Ollivier
emes
th
ph
emes
ysiques
comm
r
en


eels
elargissen
et
ort

mes
a
mais
des
olisen
th
le

t
eories
Je
math


de
ematiques
p
qui
etite
on
dite
t

une
os
histoire
.
Je

suis
qui
heureux
e
que
le
cette
t
th
ees


ese
lui
don
t
t
our
la
b
derni
part

hel
ere
etitot
ann
une

marquan
ee
du
a
quelqun
exig
v

qui
e
parle
de
on
moi

une
t
v
pr

esence
eritable
ce
apn
m

vraimen
ee
plaisir
ait
remercie

hel
et
Professeur

LIFL
e
v
consacr
pr

esid
ee
e

jury
a
th
l
ese

en
etude
rapp
dn
t
tel
rigueur
sujet
le
Mes
du
premiers

remercie
des
m

en
exp
ts

iron
dans
t
cours
donc
Licence

^
a
DEA
G
que

essa
erard

Jacob
de
Professeur

au
ce
LIFL

p
.
our
rapp
m
de
v
th
oir
ese
prop
t
os
Lazard


e
lniv
un

tra
P
v
ris
ail
et
dne
ran
telle
Ollivier
nature

et
de
m
herc
v
CNRS
oir
a
accord
P

hnique
e
rapp
une
a
grande
ec
lib
Giusti
ert
de

herc
e
CNRS
dans
Ma
sa
re
r
Conf

erences
ealisation
a
Plus
P
que
hnique
tout
tra
autre
ail
je
b
remercie
aux
Mic
don
hel
ils
P
t
etitot
part
Nous
particulier
a
remercie
v
Lazard
ons
F
pass
cois

p
e
les
ensem

ble

des
quls
heures
t
que
uniqu
je
es
ne
n
compte
th
plus
ese


a
t
faire
p
et


de
a
r
refaire
esultats
les
qui
preuv
b
es
t
de
tout
th
temps

mn
eor
consacr

e
emes
me
dlgo
ermets
rithmes
egale
et
t
bien
remercier
que
Giusti
je
our
ne
p
lie
phrase
jamais
t
men
p
tionn
apr

es
e
exp
dans

les
.
pages
.
qui
d
suiv
ebutan
en
et
t
m
les

r


garder
esultats
moral
qui
endan
y
les
son

t
os
exp
Remerciemen
tel-00137866, version 1 - 22 Mar 2007o
qui
bres
ln
en
t
aux
suivie
ensables
Je
cette
remercie
mem
Giuseppa
doiv
Carr
merci
a
t
erro
il
Professeur


premiers
a

lniv

ersit
b

soutenir
e
impriman
de
o
Catania
et
p
soutien
our
1994.
a
en
v

oir
a
accept


rapp
e
la
de
grand
particip

er
de

bureau
a
a
ce
r
jury
ese
et
cafeti
a
Merci
v

oir
a
bien
qui
v
our
oulu
de
faire
d
lrt
le
de
don
lire
preuv
cette
ermanence
th
la

de
ese
e
r



edig
faire

et
ee
encore
en

F

ran
Jdresse
cais
aux
Je
de
remercie
e
Andr
la

bulen
e
ts
Galligo
Je
Professeur
courage

ceux
a
t
lniv
ediger
ersit
th

demande
e
p
de
ere
Nice
du
de
lab
m
copains
v
au
oir
en
fait
les
lon
ma
neur
t
de
e
particip
p
er


ans
a
une
ce
energie
jury
e
.
juillet
Je
exceptionnel
remercie
t
Sette
fait
Diop
e
Charg
p

et
e
assure
de
coh
Rec
esion
herc
l
hes
equip
CNRS
Il
au
aid
LA
e
GEP
th
d
ese
v
a
oir
ses
particip
pas

me
e
elle

souv
a
t
ce
a
jury
r
.
ealit
Sa
e
th
un

merci
ese
autres
qui
bres
fut
l
le
equip
p
et
oin
a
t
quinzaine
d
tur

ts
epart
ccupan
de
du
la
214.
mienne
souhaite
m
on
p

ermis
tous
db
qui
order
en
en
encore
douceur

certains
et
textes
une
ardus

Je
Je
remercie
merci
Rudolf
trop
Bk
opulaires
ouc

he
et
Professeur
te

bureau
a
au
lFR
o
de
aux
Math
ext

erieurs
ematiques
lab
de
merci
m

v
tous
oir
mem
fait
de
lonneur
famille
de
on
particip

er


p
a
moi
ce
endan
jury
pr
.
es
Jxprime
quatre
ma
un
profonde
et
gratitude
source


a
indisp
Nourddine
Villeneuv
Oussous
dscq
p
12
our
tact
le
2
tel-00137866, version 1 - 22 Mar 2007
.
syst
T

able
3.1
des
.
mati
.

.
eres
.
In
.
tro
terminaux
duction
.
5
.
1
eition
Notions
.
dlg
.

.
ebre
.
di
.

.
eren
.
tielle
.
9
.
1.1
.
P
.
olyn
.
omes
.
di
.

.
eren
tre
tiels
.
.
2.4.1
.
.
.
r
.
.
.
d
.
eren
.
.
.
.
.
.
.
.
.

.
.
.
emes
.
3.1.5
.
.
.
.
.
.
.
46
.
.
.
3.1.8
.
.
.
ebre
.
.
.
.
.
3.2.2
.
.
.
.
10
30
1.1.1

Relations
.
drdre
.
admissibles
.
.

.
.
.
.
.
2.4.2
.
.
.
.
.
.
.
35
.
Seiden
.

.
.
.
.
.

.
.
.
.
.
.
.
D
.
.
.
.
10
.
1.1.2
des
Initiaux
.
|
.
s
dans

.
eparan
.
ts
^
.
.
.
.
.
.
.
Preuv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Llgorithme
.
tielle
.
.
.
50
.
emes
.
.
.
.
.

.
.
.
.
14
51
1.2
.
Id
.

Relations
eaux
mo
di
.

.
eren
.
tiels
.
.
.
.
.
.
.
.
bles
.
et
.
ts
.
.
.
.
.
.
.
.
.

.
eguliers
.
.
.
.
.
.
.
.
.
.
.
.
.
Les
.
elimination
.
erg
.
en
.
di
.
ordinaire
.
.
.
.
.
.
.
3.1.1
.
.
14
.
1.2.1
.
Id
.

.
eaux
.
r
.

38
esiduels
eition
.
emes
.
.
.
.
.
.
.
.
.
3.1.3
.

.

.
.
.
.
.
.
.
.
.
3.1.4
.
syst
.
.
.
.
.
.
.
.
.
e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
15
de
1.3
.
R
.

.
eduction
.
.
.
.
.
.
Optimisations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
dpplication
.
.
.
.
.
.
.
.
.
.
.
49
.
alg
.

.
.
.
.
.
.
.
.
.
D
.
syst
.
.
.
.
.
.
.
.
.
.
.

.
des
.
terminaux
.
.
16
.
1.3.1
.
R
.

.
eduction
.
par
.
un
.
p
.
olyn
2.4
ome
en
.
les
.
d
.
eles
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
.
Ensem
.
auto
.
eduits
.
coh
16
eren
1.3.2
.
Ensem
.
bles
.
auto
.

.
eduits
.
.
.
.
.
.
31
.
Syst
.
emes
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
.
algorithmes
.

.
de
20
b
2
37
Mo
Llgorithme
d
alg

ebre
eles

dn
tielle
syst
.

.
eme
.
d
.

.
equations
.
et
.
dn
38

Pr
equations
eliminaires
25
.
2.1
.
D
.

.
ecomp
.
osition
.
dn
.
id
.

.
eal
.
radiciel
.
.
.
.
.
.
.
.
3.1.2
.

.
des
.

.
terminaux
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
.
G
.
en
.
eration
.
syst
25
emes
2.2
.
Extensions
.
di
.

.
eren
.
tielles
.
.
.
.
.
.
41
.
Elimination
.
les
.

.
terminaux
.
.
.
.
.
.
.
.
.
.
.
.
.
42
.
Preuv
.
drr
.
et
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
.
2.3
.
Mo
.
d
.

.
eles
3.1.6
di
es

correction
eren
.
tiels
.
et
.
mo
.
d
.

.
eles
.
alg
.

.
ebriques
.
.
.
.
.
.
3.1.7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
.
2.3.1
.
Mo
48
d
Exemple

.
eles
.
di
.

.
eren
.
tiels
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.2
.
en
.

.
di
.
eren
.
partielle
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.2.1
.

.
des
.

.
terminaux
29
.
2.3.2
.
Mo
.
d
.

.
eles
.
alg
.

.
ebriques
50
.
G
.
en
.
eration
.
syst
.
emes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
tel-00137866, version 1 - 22 Mar 2007fait
.
.
3.2.3
A
Preuv
est
es
.
.
.
.
.
.
ecision
.
tiel
.
.
.
Les
.
des
.
Con
.
A
.
.
.
.
.
.
.
.
.
caract
.
.
.
Rosenfeldr
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
di
52
a
3.2.4
.
Elimination
.
dans
|
les
.
syst
.

.
emes
dnsem
terminaux
.
|
.
Preuv
.
es
a
.
.
.
.
.
.
.
.
.
.
.
ees
.
.
54
application
4
.
Bases
.
de
.
Gr
de
obner
.
|
.
Ensem
5.3
bles
.
caract
.

.
eristiques
74
57
.
4.1
.
Bases
.
de
.
Gr
dn
obner
.
alg
T

eal
ebriques
.
.
Calcul
.
.
.
.
.
Implan
.
Les
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
eristique
.
.
.
.
.
.
.
.
.
.
.
.
.
6.3
.

.
.
.
.
58

4.1.1
.
Pr
.


eliminaires
.
.
.
.
.
.
.
.
ebriques
.
.
.
.
.
.
.
sessions
.
non
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
110
.
.
.
.
.
que
.
.
.
.
.
.
.
.
.
.
58
.
4.1.2
.
Bases
D
de
vide
Gr
.
obner
.
.
.
.
.
.
.
.
.
.
5.3.2
.
au
.

.
eren
.
.
.
74
.
dppartenance
.
id
.

.
.
.
.
.
74
.
ensem
.
eristique
.
.
.
.
.
.
.
76
.
|
.
80
.
.
.
.
60
.
4.1.3
.
Th
.

.
eor
.

.
emes
6.1.1
utiles
.
.
.
.
.
.
.
.
.
.
6.1.2
.
caract
.
.
.
.
.
.
.
.
.
83
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
application
.
non
.
.
.
.
.
.
.
.
61
6.4
4.2
de
Bases
.
de
.
Gr
.
obner
.
di
.

6.5
eren
du
tielles
.
.
.
.
.
.
.
.
.
.
.
.
.
.
93
.
alg
.
h
.
.
.
.
.
.
.
.
.
.
.
Conclusion
.
s
.
A
.
a
.

.
.
.
.
.
.
63
.
4.2.1
duler
M
.

.
etho
.
de
.
de
.
Ollivier
.
.
.
.
A
.

.
taire
.
.
.
.
.
.
.
.
.
.
.
.
.
118
.
121
.
.
.
.
.
73
.
Ce
.
llgorithme
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
64
.
4.2.2
.
M
.

.
etho
.
de
.
de
5.3.1
Mansld

.
du
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
74
.
T
.
dppartenance
.
radical
.
id
.
eal
.

.
tiel
.
.
65
.
4.3
.
Ensem
5.3.3
bles
est
caract


un
eristiques

dd
di

eren
eaux
premier
.
.
.
.
.
.
.
.
.
5.3.4
.
dn
.
ble
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
.
tations
.
Applications
.
Comparaisons
65
6.1
5
algorithmes
Repr
.

.
esen
.
tation
.
des
.
mo
.
d
.

.
eles
.
di
.

.
eren
.
tiels
.
dn
.
syst
.

80
eme
Algorithme
68
obner
5.1
.
G
.

.
en
.

.
eration
.
des
.
syst
.

.
emes
80
r
Calcul

ble
eguliers

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6.2
.
logiciels
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
69
.
5.1.1
.
Preuv
.
e
.
drr
.
^
.
et
84
.
Une
.

.
lutomatique
.
lin
.
eaire
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
89
.
Calcul
.
conditions
.
compatibilit
.
e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
91
.
D
71
ecision
5.1.2
vide
Preuv
.
es
.
de
.
correction
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6.6
.
tradictions
.

.
cac
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
71
.
5.1.3
.
Syst
95

97
eme
Exemple
principal
de
asso
99
ci
Une


e
lutomatique

lin
a
eaire

.
.
.
.
.
.
.
.
.
.
.
.
.
.
99
.
Equations
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
72
.
5.2
.
Calcul
.
des
.
bases
107
de
G
Gr
en
obner
eration
.
commen
.
s
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Bibliographie
.
Index
.
.
4
tel-00137866, version 1 - 22 Mar 2007app
la

tro
du
duction
second
Le
de
but
etation
de
outils
cette
preuv
th
sous

ees
ese
t
est
informations
de
exigeait
rendre
ees
ectifs
compr
certains

th
o


eor
ud

premi
emes
a
et
praticable
dmplan
eme
ter
bases
eacemen
son
t
ealiser
certains
dacit
algorithmes
donner
en
r
alg
ebre

es
ebre
aux
di


de
eren
accessible
tielle
a
en
ten
vue

dne
]
applica

tion
des

simples
a

lutomatique
:
non
un
lin
la

esultats
eaire
des
Nous
obner
pr
de

leur
esen

tons
ail
trois
con
r
des


esultats
sp
originaux
terpr
Le
moins
premier
des
est
tielle
un
algorithmes
algorithme
optimisations
qui
part
d


p
ecrit

les
et
mo
et
d
moins

eoph
eles
ons
dn
des
syst
]

dans
eme

d
Les

D
equations
b
et

dn
ecriture

ere
equations
tr
p

olynomiales
t
en
la
alg
dne

v
ebre
algorithme
di
jusqu

p
eren
seconde
tielle
m
ordinaire
r
comme
duits
en

alg
rithmes

Gr
ebre
exemple
di
par

g
eren
pas
tielle
terpr
partielle
pas
Llgorithme
R
d
tra


ecide
ces
du
sans
vide
e
et

donc
du
de
puis
lppartenance
implan
au
ecialis
radical
dn
dn
eter
id
esultats

partie
eal
dne
di
dlg


eren
our
tiel
ehension
de
les
t
correction
yp
nous
e
;
i
tra
Notre
les
deuxi
de


eme
les
r
de

et
esultat
drr
est
les
une
i
m
K

premier
etho
mais
de
n
qui
que
calcule
a
un

ensem
ec
ble
in
caract
s

leur
eristique
ure
dn
],
id
forme


eal
plus
di
de

Dersho
eren
Comon
tiel
on
premier

donn
en

de
e

par
la
une

famille
puisque
g
en


en
tr

es
eratrice
parviennen
Nous

donnons
saturer
en
m
de
emoire
nouv
station
elles
tra
preuv
ail
es
cet
des
nst
algorithmes
que
d
a

certain
elimination
oin
de
La
Seidenber
est
g
nature
.
^
Les
des
algorithmes

que
pro
nous
A
d
di

erence
ecriv
algo
ons
de
son
de
t

ectifs
par
:
les
ils
fournies
ntilisen
llgorithme
t
Seidenber
que
ne
lddition
t
la
standard
m
in
ultiplication

les
nst
d
ais

ee
eriv

ations
le
et
v
le
demand
test
e
d
dptimiser

algorithmes
egalit
cus

souci
e


par
a
alg
z
ebristes

milieu
ero
si
dans
ecle
le
dn
corps
des
de
tations
base

des

p
capables
olyn
in
omes

En
les
o

ctobre
au
1990,
en
mon
Nos
directeur
:
de
part
th
ouvrages


ese
di
m
eren
prop
p
os
la


e
des
|
et
dans
preuv
le
de
cadre
des
dn
que
do
leur
ctorat
ortions
en
dutre
informatique
des
|
v
dmplan
sur
ter
syst
eacemen
emes
t
r
certains
e
algorithmes
ecriture
dlg
our

probl
ebre
emes
di
canonicit

e
eren
les
tielle
es
en
^
vue
Citons
dne
livres
application
Ritt

]
a
de
lutomatique
olchin
non
Le
lin
est

complet
eaire
plus
Llgorithme
aux
d


ytes
elimi
le
nation
Nous
de
v
Seidenber
consult
g
e
en
v
alg
pro

articles
ebre
term
di
ediaire

o
eren
:
tielle
con
ordinaire
u
par
bien
lequel
o
cette
mais

une
etude
g
a
en
commenc
eralis

ee
e
abrupte
illustre
textes
parfaitemen
Jouanna
t
,
les
witz
diult
et

o
es
nous
auxquelles
t
nous
eaucoup
nous
eclair
sommes
e
heurt
mati

ere
es
r
Lxplosion
e
com
est
binatoire
In
tel-00137866, version 1 - 22 Mar 2007de
emes

In
t
tro

duisons
.
main
algo
tenan
les
t
que
plus
engendr
tec
ectiv
hniquemen
aien
t

notre
e
sujet
emes
G
Un

d
en
du

eren
eralisan
ner
t
r
un
en
th
on

eaux
eor
ces

notre
eme
ations
de
corps
1956,
une
d
mo
^
erin
u
alg


a
de
Seidenber
,
g
th
e
au
],
ld
un
premi
math
algorithme

I
ematicie
En
n

am


notammen
e
ces
ricain
bles
R
es
osenfeld
ces
,
lues
donne

en
ep
1959
les
une
d
condition

suan

te
eme
o
)
o
t
p
que
our
emen
qun
de
syst
de

p
eme
les
d


mo
equations
i
p
osenfeld
olynomiales
Il
di
dpr

eme
eren
t
tielles

admette
yp
un

mo

d
de

pro
ele
un
ne
de
solution

dif
Olli
f
Gr

breuses
eren
syst
tielle

sl
sortie
admet
de
un
breux
mo

d


lues
ele
tiques
puremen
tiels
t
equations
alg
eliorons

nous
ebrique
en
Ce
la
th
lnsem

Lriginalit
eor
cst

ciessus
eme
ultipli
est

le
le
l
egalit
conducteur
a
de
dans
cette
base
th
P

syst
ese
llgorithme
P
(

our
syst
lllustrer
y
consid
^


erons
don
le
el
syst
v

la
eme
osenfeld
di
de


eren
ebrique
tiel
alors
suiv

an
tradictions
t
cac
en
et
deux
ecrire
ind


haque
etermin
Cet

nommons
ees

u
trois
et

v
et
,
es
o
eor


u
de
les
de
deux
dn
d
di

de
eriv
i
ations
eal

tiel
x
e
et
premier

ere
y

son
con
t
par
not
ermet

ble
ees
u
en
)
indice
Nous
:
ainsi

esultat
8
l
>
R
<
obner
>
de
:

u
structurelles
x
emes
=
non
0
bserv
u
rang
y
.
v
Sous
=
[F
0
de
v
herc
x
mon
=
commen
1

Le
p
syst
^

les
eme


id
ne

v
engendr

les
eri
syst
pas
am
la
p
condition
hniques
de
trons
R
p
osenfeld
^
puisqul
t
admet
de
un
de
mo
e
d
est

e
ele
v
alg
r

aux
ebrique
un
mais
m
pas
cation
de
d
mo
eriv
d
et

test
eles

di



eren
z
tiels
ero
En
le
et
de
si
des
on
equations
d
artan

dn
eriv

e
,
la
construit
premi
famille

i
ere
de


equation
a
par
an
rapp
m
ort
emes

d
a
eles
x
,
,
t
la

deuxi


ts
eme

par
t
rapp
condition
ort
R

.
a
calcul
y
bases
et
Gr
si
obner
on

soustrait
classique
les
ermet
p
et
olyn
d
omes
etecter
obten
con
us
alg
u
ebriques
xy
h
(
ees
u
de
xy

v
les
x
d
)
eles
=
c
v

x
.
on
algorithme
obtien
nous
t
R
une
Gr
relation
obner
qui
a
con
applications
tredit
d
la
ecide
troisi
vide

donc
eme


un
equation

du

syst
c

el
eme
ebre
:
Hilber

,
ndmet
lppartenance
pas
radical
de
id
mo
eal
d


tiel
eles
t
di
e

Lorsque
eren

tiels
di
P
eren
ar
[]
con

tre
par
si
est
on
la
oublie

que
base
les
Gr

ob
equations
non
son
tradictoire
t
duite
di
notre

p
eren
dxtraire
tielles
ensem
et
caract
si
eristique
on
sens
les
Ritt
in
de
terpr
.

am
ete
eliorons
comme
un
des


de
equations
vier
puremen
].
t
llgorithme
alg
osenfeld


ebriques
rend
en
es
quatre
nom
ind
propri

et
etermin
es

des
ees

u
dynamiques
x
automatique
,
lin
u
eaire
y
abilit
,
e
v
de
et
etc
v
.
x
).
,
lmpulsion
le
Fliess
syst
]

t
eme
nom
admet
c
un
heurs
mo
t
d
tr

e
ele
t
alg
propri

et
ebrique
es
trivial
ouv
F
t
ond
etre

dans
e
ensem
sur
caract
le
eris
lemm
des
e

de
di
R
eren
osenfeld
premiers
,

notre
par
premier

r
des


esultat
Nous
est

un
un
algorithme
eu
qui
tec
d
puisque

mon
ecrit
que
les
informations
mo
euv
d
t

etres
eles
directemen
dn
dans
syst
base

Gr
eme
obner
d
laquelle

bl
equations
caract
p
eristique
olynomiales
extrait
di


de
eren
tra
tielles
ail
en
de
nmplo

y
ondre
an
questions
t
par
que
la
lddition
6
tel-00137866, version 1 - 22 Mar 2007mo
tr
nation
rithme
plexit
qui
d
pro
de
duit
que
un
eraux
r


ari
esultat
preuv
i
g
en
osenfeld
un
qui
nom

bre
eciden
i
er
d
t

est
etap
au
es
une
de
ebre
calcul

et
eren
qui
sur
nmploie
complexit
que
tielle
lddition
dne
la
conn
m
er
ultiplication
nation
les

d
en

corps
eriv
enien
ations
relations
et
dynamique
le
jections
test
di
d


tielle
egalit


nation
e
ulons


a
th
z
etait

de
ero
e
dans
une
le
us
corps
obn
de
mination
base
e
des


de
equations
n
P
famille
our

mieux
g
situer
algorithmes
notre
e
app
syst
ort
eren
d
di

R
ecriv
op
ons

en
deux
quelques
part
mots
de
les
en
principales
un
m
leur

calculen
etho
es
des
e
existan
asso
tes
Diop
Ritt
llgorithme
a
ebre
donn
a

lutomatique
e
aussi
i
d
]
.
une
tielle
m
gr

ce
etho
le
de
emes
p
eme
our
es
d


aux
ecomp
fournissons
oser
du
le
nation
radical
de
dn
du
id
sommes


eal
llgorithme
di
celle

algorithmes
eren
ebre
tiel
[G]
en
llgorithme
une

in
Lazard
tersection
presquptimale
dd
qui

t
eaux
meille
di
la


eren
de
tiels
consid
premiers
e
P
en
i
t
,

en
Seidenber
fournissan
d
t
si
un
eme
ensem
di
ble
admet
caract


eren
eristique
t
p

our
que
c
erations
hacun
base
des
Ils
P
ten
i
v
.
:
Cet
p
algorithme
en
qui
er
en
lien
ait
les
plus
ecrites
que

le
dutre
n
ortemen
otre
parce
pr
des

blistes
esen
la
te
et
lncon

v
eren


enien

t
i
de

n

^
alg
etre

que
et
partiellemen

t

ectif
cette
puisqul
nous
pro
nouv
c
des

elimi
ede
Seidenber

alg
a

des
nous
fac
preuv
torisations
au
suiv
osenfeld
an
in
t
llgorithme
des
des
tours
r
dxtensions
:
alg
eor

de
ebriques
tr
du
hnique
corps
En
des
di
co
ordinaire
eien
v
ts
,
A
preuv
notre
es
connaissance

il

n

jamais
lemm

qui
et
ersion

de
e
Nous
implan
parv
t
a

ni
e
e
Ollivier
osenfeldr
l
,
]
v
et
donnons
Carr


alg
aerr

o
Grigor
a
donn
on
optimisation
t

ind
app

une
ep
de
endemmen
qui
t

ten
;
t
v

une
e
e
de
onen
g
fournit

b
en
p

le
eraliser
g

en
a
eratrice
llg
ld

eal
ebre

di


Plus
eren

tielle

les
son
bases
les
de
d
Gr
elimi

de
obner
g
in
Ils
v

en
t
t
un


ees
d
par
equations
Buchber

ger
tielles
u
des
]
d
p
eles
our

l
tiels

ntilisan
etude
comme
des
osenfeldr
id
obn

,
eaux
les
de

p
du
olyn
de
omes
des
en
equations
alg
pr

esen
ebre
t
comm
incon
utativ

e
ts
Ces
dne
bases
ils
de
ermetten
Gr
diilem

t
obner
trouv
dif
les
f
qui

t
eren
trlles
tielles
grandeurs
son

t
par
dgr
syst

eme
eables
et
repr
part

comp
esen
t
tan
explosif
ts
quls
des
t
id
pro

ensem
eaux
successiv
di
de

v
eren

tiels

qulles
alg
engendren
ebrique
t

trop
tielle
agr
ci

ee
eables
syst
p
eme
eut
i
^
a
etre
etudi
car
e
lppartenance
d

elimi
a
en
un

id
di

eren
eal
ordinaire
di
en

donn
eren
e
tiel
application
quelconque
a
est
Dans
un
th
probl
ese

donnons
eme
de
ind
elles

es
ecidable
algorithmes
MO

lppartenance
-

de
a
g
un
En
id


di
eal
eren
de
partielle
t
reform
yp
la
e
e
i
ace
est
lemme
un
R
probl
,

qui
eme
t
ouv
egre
ert
dans
et
giron
les
th
bases
eo
de

Gr
classiques

le
obner

di


original
eren
Seidenber
tielles
,
ainsi

d
tec


eies
marginal
son
alg
t
ebre
en

g
tielle

suite
en
tra

aux
eral
Diop
inies
nous
Plus
une
r
e


ecemm
simple
en
m
t
ecanism
Mansfield
d
[M1]
elimi
a
fond
donn
ee

un
e
e
une
Ritt
d
est

v
eition
faible
de
lemme
bases
R
de
.
Gr
ne

encore
obner
en
di


d
e
eterminer
ren
la
tielles

moins
de
pro
R
c

he
er
de
ni
celles
des
de
ersions
Buchber
nous
ger
des
et
d
moins
eli
satisfaisan
En
te

que
di
celles
eren
de
ordinaire
Ollivier
v
et
a
Carr


une
aerr
de
o
d
.
elimination
Llgorithme
fait
prop
el
os
a

m
e
etho
par
de
Mansfield
[L1],
calcule
est
une
complexit
base
e
ie
[L3]
en
llgorithme
un
Grigor
nom
,
bre
a
i
com
d


triplemen
etap
exp
es
tielle
de
temps
calculs
la
mais
ure
imp
orne
ose
ue
des
our
restrictions
sur
7
tel-00137866, version 1 - 22 Mar 2007