Reference : Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps fini
Dissertations and theses : Doctoral thesis
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/11381
Caractère reconnaissable d'ensembles de polynômes à coefficients dans un corps fini
French
Waxweiler, Laurent mailto [Université de Liège - ULg > > > Doct. sc. (math. - Bologne)]
11-Dec-2009
Université de Liège, ​Liège, ​​Belgium
Docteur en sciences
xi, 131
Rigo, Michel mailto
Lecomte, Pierre mailto
Hansoul, Georges mailto
Berthé, Valérie mailto
Bès, Alexis mailto
[fr] 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
[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).
Researchers ; Professionals ; Students ; General public ; Others
http://hdl.handle.net/2268/11381

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
ThèseWaxweilerLaurent.pdfNo commentaryAuthor postprint882.34 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.