AUTOMATES ET MOTS STURMIENS / FILIPPO MIGNOSI ; SOUS LA DIRECTION DE DOMINIQUE PERRIN

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 1991

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Perrin, Dominique (1946-....) (Directeur de thèse / thesis advisor)

Université Paris Diderot - Paris 7 (1970-2019) (Organisme de soutenance / degree-grantor)

Résumé / Abstract : CETTE THESE SE PROPOSE D'ETUDIER CERTAINS PROBLEMES DE LA COMBINATOIRE DES MOTS, EN PARTICULIER CE QUI CONCERNE L'ETUDE DES FACTEURS, OU SOUS-SUITES CONSECUTIVES, DANS LES MOTS. DANS LA COMBINATOIRE DES MOTS, LA NOTION DE MOT STURMIEN S'EST IMPOSEE NATURELLEMENT A L'ESPRIT DES CHERCHEURS DEPUIS AU MOINS DEUX SIECLES. LES MOTS STURMIENS SONT EXTREMAUX DANS LE SENS QU'ILS ONT LE NOMBRE MINIMAL DE FACTEURS POSSIBLES SANS ETRE PERIODIQUES. ILS PEUVENT ETRE INTRODUITS GEOMETRIQUEMENT COMME INTERSECTION D'UNE DROITE AVEC UN QUADRILLAGE. LA THESE EST COMPOSEE DE SEPT CHAPITRES, SOIT PUBLIES SOIT PARUS COMME RAPPORT INTERNE DU LABORATOIRE D'INFORMATIQUE THEORIQUE ET PROGRAMMATION. LE PREMIER CHAPITRE A POUR OBJET L'ENSEMBLE DES MOTS INFINIS DONT LE NOMBRE DE FACTEURS CROIT DE FACON AU PLUS LINEAIRE (LES MOTS STURMIENS APPARTIENNENT A CET ENSEMBLE). ON MONTRE QUE CES MOTS POSSEDENT LA PROPRIETE DITE DE PERMUTATION FAIBLE, PROPRIETE QUI A ETE BEAUCOUP ETUDIEE SUITE A UN ARTICLE FONDAMENTAL DE RESTIVO ET REUTENAUER. EN OUTRE, POUR LES MOTS STURMIENS, ON RELIE LA PROPRIETE D'ETRE SANS PUISSANCE K-IEME AU DEVELOPPEMENT EN FRACTION CONTINUE DE LA PENTE DE LA DROITE ASSOCIEE; POUR QU'IL EN SOIT AINSI, IL FAUT ET SUFFIT QU'UN TEL DEVELOPPEMENT SOIT A QUOTIENTS PARTIELS BORNES. LE DEUXIEME CHAPITRE ETUDIE LES PROPRIETES DES LANGAGES ASSOCIES AUX MOTS STURMIENS. APPELONS POUR UN REEL X DE L'INTERVALLE 0,1, A(X) L'ENSEMBLE DE FACTEURS DE MOTS STURMIENS CORRESPONDANT A UNE DROITE DE PENTE POSITIVE ET INFERIEURE OU EGALE A X (CE N'EST PAS TOUT A FAIT LA PENTE MAIS CELA Y EST LIE DE MANIERE SIMPLE). ON CALCULE LA FONCTION DE COMPLEXITE DU LANGAGE A(X) (ON RESOUT AINSI LA CONJECTURE DE DULUQ ET GOUYOU-BEAUCHAMPS SUR LA FONCTION DE COMPLEXITE DU LANGAGE A(1). ON MONTRE L'ETROITE CONNEXION ENTRE CES FONCTIONS DE COMPLEXITE ET LES SUITES DE FAREY ET ON PEUT AINSI DONNER UN EQUIVALENT PUREMENT COMBINATOIRE DE L'HYPOTHESE DE RIEMANN. DANS LE TROISIEME CHAPITRE ON MONTRE QUE: A) POUR TOUT X LA FONCTION GENERATRICE ASSOCIEE AU LANGAGE A(X) EST TRANSCENDANTE, B) SI X EST RATIONNEL, LE COMPLEMENTAIRE DE A(X) EST UN LANGAGE ALGEBRIQUE. (A) MONTRE, EN VERTU DU THEOREME DE CHOMSKY-SCHUTZENBERGER QUE LE COMPLEMENTAIRE DE A(X) NE PEUT PAS ETRE ALGEBRIQUE NON AMBIGU; (B) DONNE EN PARTICULIER UNE VERSION DE L'HYPOTHESE DE RIEMANN EN TERMES DE FONCTION DE COMPLEXITE DE LANGAGES CO-ALGEBRIQUES