Doctoral thesis (Dissertations and theses)
Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps fini
Waxweiler, Laurent
2009
 

Files


Full Text
ThèseWaxweilerLaurent.pdf
Author postprint (903.51 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
polynôme; corps fini; automate fini déterministe; reconnaissable; P-reconnaissable; théorème de Cobham; ensemble syndétique; définissable; P-définissable; multiplication (P-Q)-définissable; suite automatique; suite P-automatique; P-noyau fini
Abstract :
[fr] Nous nous plaçons dans le cadre de l'anneau des polynômes sur un corps fini. Si P est un polynôme de degré au moins 1, tout polynôme Q se décompose de manière unique sous la forme d'une combinaison linéaire de puissances de P, dont les coefficients sont des polynômes dont le degré est strictement inférieur à celui de P. À une telle décomposition, nous associons un mot que nous appelons la P-représentation du polynôme Q. Un ensemble de polynômes est alors qualifié de P-reconnaissable si il existe un automate fini déterministe qui accepte l'ensemble des P-représentations de ses éléments. Dans cette thèse, nous montrons que les ensembles P-reconnaissables sont exactement ceux qui sont définissables par une formule du premier ordre dans une certaine structure S(P) basée sur un prédicat dépendant du polynôme P. Nous donnons aussi une caractérisation des ensembles P-reconnaissables en terme de suites P-automatiques. Nous apportons également une réponse partielle à la question de savoir quels sont les ensembles reconnaissables simultanément dans toutes les bases de degré au moins 1. Finalement, nous montrons que si P et Q sont deux polynômes de degré au moins 1 et multiplicativement indépendants, alors la multiplication est définissable dans la réunion des structures S(P) et S(Q).
Disciplines :
Mathematics
Author, co-author :
Waxweiler, Laurent ;  Université de Liège - ULiège > Doct. sc. (math. - Bologne)
Language :
French
Title :
Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps fini
Defense date :
11 December 2009
Number of pages :
xi, 131
Institution :
ULiège - Université de Liège
Degree :
Docteur en sciences
Promotor :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique
President :
Lecomte, Pierre ;  Université de Liège - ULiège > Département de mathématique
Secretary :
Hansoul, Georges ;  Université de Liège - ULiège > Département de mathématique
Jury member :
Berthé, Valérie
Bès, Alexis
Available on ORBi :
since 22 January 2010

Statistics


Number of views
321 (31 by ULiège)
Number of downloads
430 (22 by ULiège)

Bibliography


Similar publications



Contact ORBi