Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux. Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur , celle pour les mots de longueur inférieure à , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable. Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur aux mots de longueur inférieure à , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les -semigroupes et les -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable. Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

L'objectif de cette thèse est de représenter les émotions spontanées et les signes multimodaux associés pour contribuer à la conception des futurs systèmes affectifs interactifs. Les prototypes actuels sont généralement limités à la détection et à la génération de quelques émotions simples et se fondent sur des données audio ou vidéo jouées par des acteurs et récoltées en laboratoire. Afin de pouvoir modéliser les relations complexes entre les émotions spontanées et leurs expressions dans différentes modalités, une approche exploratoire est nécessaire. L'approche exploratoire que nous avons choisie dans cette thèse pour l'étude de ces émotions spontanées consiste à collecter et annoter un corpus vidéo d'interviews télévisées. Ce type de corpus comporte des émotions plus complexes que les 6 émotions de base (colère, peur, joie, tristesse, surprise, dégoût). On observe en effet dans les comportements émotionnels spontanés des superpositions, des masquages, des conflits entre émotions positives et négatives. Nous rapportons plusieurs expérimentations ayant permis la définition de plusieurs niveaux de représentation des émotions et des paramètres comportementaux multimodaux apportant des informations pertinentes pour la perception de ces émotions complexes spontanées. En perspective, les outils développés durant cette thèse (schémas d'annotation, programmes de mesures, protocoles d'annotation) pourront être utilisés ultérieurement pour concevoir des modèles utilisables par des systèmes interactifs affectifs capables de détecter/synthétiser des expressions multimodales d'émotions spontanées.

Les systèmes de question- réponse monolingues ou multilingues permettent de chercher dans une grande collection de documents (de type journalistique par exemple), ou sur le Web une réponse précise à une question. Cependant, il n'y a pas d'interaction possible après la réponse : on ne peut pas demander une précision, modifier sa question. Or souvent la réponse ne peut pas être apportée directement (question trop imprécise), ou n'est pas pleinement satisfaisante pour l'utilisateur. Le sujet de la thèse proposée consiste à étendre ces travaux de manière à permettre à un utilisateur d'engager un vrai dialogue, qui ne se réduise pas à une question/une réponse, en se fondant sur le travaux menés dans le cadre du dialogue homme-machine. Le contexte de cette thèse se situe dans le prolongement des travaux menés dans le groupe LIR du LIMSI. En effet, nous travaillons depuis plusieurs années sur les systèmes de Question-Réponse, et nous avons participé à plusieurs campagnes d'évaluation, tant sur le monolingue anglais (campagne TREC-QA : http: / / t rec.nist.gov/), que sur le monolingue français (campagne EqueR-EVALDA : http: / /www.elda.org/article118.html) ou sur le multi-lingue (campagne CLEF-QA : http: / / clef- qa.itc.it /). Ces campagnes présentent l'intérêt de permettre une évaluation de nos travaux par rapport à la communauté nationale et internationale. Elles nous ont également permis d'en mesurer les limites et de définir des champs de recherche très ouverts, que ce soit au niveau de notre groupe ou des perspectives envisagées dans le cadre même de ces campagnes d'évaluation. Par ailleurs, nous avons longtemps travaillé sur les systèmes de dialogue homme-machine, plus ou moins finalisés. Le cadre des systèmes ouverts (sans tâche définie a priori) que constitue la recherche dans des grandes collections de documents ou sur le web nous permet de reprendre et d'étendre ces travaux. Le but de cette thèse est donc d'ouvrir les systèmes de question/ réponse à un dialogue au cours duquel n'importe quel sujet peut être abordé. Le point de départ est une adaptation des travaux menés en dialogue Homme-Machine dans des domaines restreints à un système de Questions-Réponses. Ces recherches ont pour finalité d'apporter des perspectives nouvelles au moteur de recherche d'information classique, à la fois en terme de précision de l'information trouvée, de volume d'information traitées et de gain de temps pour accéder à cette information.

De grands corpus oraux comprenant des accents régionaux du français deviennent aujourd'hui disponibles : leurs données offrent une bonne base pour entreprendre l'étude des accents. Les outils de traitement automatique de la parole permettent de traiter des quantités de données plus importantes que les échantillons que peuvent examiner les experts linguistes, phonéticiens ou dialectologues. La langue française est parlée dans de nombreux pays à travers le monde. Notre étude porte sur le français d'Europe continentale, excluant ainsi des territoires comme le Québec, l'Afrique francophone ou encore les départements d'Outre-Mer. Nous étudierons des accents régionaux de France, de Belgique et de Suisse romande. Quelles sont les limites géographiques à l'intérieur desquelles il est possible d'affirmer que les locuteurs ont le même accent ? La réponse à cette question n'est pas évidente. Nous avons adopté la terminologie suivante, adaptée à nos données : nous parlerons d'accent lorsque nous ferons référence à une localisation précise telle qu'une ville ou une région donnée ; nous utiliserons le terme variété pour désigner un ensemble plus vaste. Bien que de nombreuses études décrivent les particularités des accents du français, il existe moins de travaux décrivant la variation de la langue dans son ensemble, et encore moins du point de vue du traitement automatique. De nombreuses questions restent ouvertes. Combien d'accents un auditeur natif du français peut-il identifier ? Quelles performances un système automatique pourrait-il atteindre pour une tâche identique? Les indices décrits dans la littérature linguistique comme caractéristiques de certains accents peuvent-ils être mesurés de manière automatique ? Sont-ils pertinents pour différencier des variétés de français ? Découvrirons-nous d'autres indices mesurables sur nos corpus ? Ces indices pourront-ils être mis en relation avec la perception ? Au cours de notre thèse, nous avons abordé l'étude de variétés régionales du français du point de vue de la perception humaine aussi bien que de celui du traitement automatique de la parole. Traditionnellement, nombre d'études en linguistique se focalisent sur l'étude d'un accent précis. Le traitement automatique de la parole permet d'envisager l'étude conjointe de plusieurs variétés de français : nous avons voulu exploiter cette possibilité. Nous pourrons ainsi examiner ce qui diffère d'une variété à une autre, ce qui n'est pas possible lorsqu'une seule variété est décrite. Nous avons la chance d'avoir à notre disposition un système performant d'alignement automatique de la parole. Cet outil, qui permet de segmenter le flux sonore suivant une transcription phonémique, peut se révéler précieux pour l'étude de la variation. Le traitement automatique nous permet de prendre en considération plusieurs styles de parole et de nombreux locuteurs sur des quantités de données importantes par rapport à celles qui ont pu être utilisées dans des études linguistiques menées manuellement. Nous avons automatiquement extrait des caractéristiques du signal par différentes méthodes ; nous avons cherché à valider nos résultats sur deux corpus avec accents. Les paramètres que nous avons retenus ont permis de classifier automatiquement les locuteurs de nos deux corpus.

Notre travail se positionne dans la thématique du traitement automatique du langage et plus précisément des systèmes de question-réponse. Il se fonde sur la notion de justification, qu'il formalise dans un modèle faisant intervenir trois types de phénomène linguistiques : les variations paradigmatiques locales d'un terme (sémantiques, morphologiques, inférences), les liens syntagmatiques entre les constituants d'une phrase, et une composante de sémantique énonciative reliant des éléments distants (anaphores, coréférences, thématisation), dans un contexte multiphrase, aussi bien mono- que multi-documents. Nous fondons notre formalisation de la structure des justifications sur un corpus de couples question-réponse extrait de façon semi-automatique. Ensuite, nous décrivons et évaluons un programme extrayant d'articles de journaux justifications structurées. Notre programme vise à conserver au système la capacité de produire une justification structurée, tout en rendant possible l'intégration modulaire d'une grande hétérogénéité de traitements linguistiques, de nature, de niveau de granularité et de fiabilité variés.

La détection de fermeture de boucle est cruciale pour améliorer la robustesse des algorithmes de SLAM. Par exemple, après un long parcours dans des zones inconnues de l'environnement, détecter que le robot est revenu sur une position passée offre la possibilité d'accroître la précision et la cohérence de l'estimation. Reconnaître des lieux déjà cartographiés peut également être pertinent pour apporter une solution au problème de la localisation globale, ou encore pour rétablir une estimation correcte suite à un

La cryptographie est devenue indispensable afin de garantir la sécurité et l'intégrité des données transitant dans les réseaux de communication modernes. Ces deux dernières décennies, des cryptosystèmes très efficaces, sûr et riches en fonctionnalités ont été construits à partir de variétés abéliennes définies sur des corps finis. Cette thèse contribue à certains aspects algorithmiques des variétés abéliennes ordinaires touchant à leurs anneaux d'endomorphismes. Cette structure joue un rôle capital dans la construction de variétés abéliennes ayant de bonnes propriétés. Par exemple, les couplages ont récemment permis de créer de nombreuses primitives cryptographiques avancées ; construire des variétés abéliennes munies de couplages efficaces nécessite de choisir des anneaux d'endomorphismes convenables, et nous montrons qu'un plus grand nombre de tels anneaux peut être utilisé qu'on ne pourrait croire. Nous nous penchons aussi le problème inverse qu'est celui du calcul de l'anneau d'endomorphisme d'une variété abélienne donnée, et qui possède en outre plusieurs applications pratiques. Précédemment, les meilleures méthodes ne résolvaient ce problème qu'en temps exponentiel ; nous concevons ici plusieurs algorithmes de complexité sous-exponentielle pour le résoudre dans le cas ordinaire. Pour les courbes elliptiques, nous algorithmes sont très efficaces, ce que nous démontrons en attaquant des problèmes de grande taille, insolvables jusqu'à ce jour. De plus, nous bornons rigoureusement la complexité de notre algorithme sous l'hypothèse de Riemann étendue. En tant que sous-routine alternative, nous nous considérons aussi une généralisation du problème du sac à dos dans les groupes finis, et montrons comment il peut être résolu en utilisant peu de mémoire. Enfin, nous généralisons notre méthode aux variétés abélienne de dimension supérieure, ce qui nécessite davantage d'hypothèses heuristiques. Concrètement, nous développons une bibliothèque qui permet d'évaluer des isogénies entre variétés abéliennes ; en utilisant cet outil important dans notre algorithme, nous appliquons notre méthode généralisée à des exemples illustratifs et de tailles jusqu'à présent inatteignables.

L'argumentation est considérée comme un modèle de raisonnement basé sur la construction et l'évaluation d'arguments. Ces derniers sont sensés soutenir/expliquer/attaquer des assertions qui peuvent être des décisions, des avis, etc... Cette thèse contient trois parties. La première concerne la notion d'équivalence de systèmes d'argumentation. Nous avons proposé différents critères d'équivalence, étudié leurs liens et montré sous quelles conditions deux systèmes sont équivalents selon les critères proposés. La notion d'équivalence est ensuite utilisée pour calculer les noyaux d'un système d'argumentation. Un noyau est un sous-système fini d'un système d'argumentation et équivalent à celui-ci. La deuxième partie de la thèse concerne l'utilisation des préférences dans l'argumentation. Nous avons étudié les rôles que les préférences peuvent jouer dans un système d'argumentation. Deux rôles particuliers ont été identifiés. Nous avons montré que les travaux existant ont abordé seulement le premier rôle et les approches proposées peuvent retourner des résultats contre-intuitifs lorsque la relation d'attaque entre arguments n'est pas symétrique. Nous avons développé une approche qui pallie ces limites. La troisième partie applique notre modèle d'argumentation à la décision et à la négociation. Nous avons proposé une instanciation de notre modèle pour la décision argumentée. Puis, nous avons étudié la dynamique de cette instanciation. Plus précisément, nous avons montré comment le statut des options change à la lumière d'un nouvel argument. Nous avons également employé notre modèle afin de montrer les avantages de l'argumentation dans des dialogues de négociation.

Dans ce mémoire, je présente une synthèse de mes travaux de recherche ainsi que le choix des thèmes étudiés. J'ai choisi de présenter trois thèmes. Les résultats obtenus pour chaque thème dépendent à la fois de la difficulté des problématiques étudiées, du temps qui leur est imparti et des circonstances et des opportunités d'encadrement des étudiants. Ces thèmes sont essentiellement sur les problèmes d'ordonnancement et principalement sont axées sur les ateliers de type flowshop avec prise en compte de contraintes supplémentaires, proche de la réalité industrielle, à savoir, (i) prise en compte de contraintes de groupement des tâches, connues sous le terme anglais, batch scheduling, (ii) prise en compte de contraintes temporelles sur la succession d'exécution des tâches, connues sous le nom de time-lags, (iii) prise en compte de la détérioration des tâches. Notre contribution à ces trois thèmes concerne d'une part l'étude de la complexité de la structure combinatoire de ces problèmes, et d'autre part la mise en œuvre de méthodes d'optimisation efficaces pour la résolution. Ce mémoire se termine par une conclusion générale, ainsi que les perspectives et les orientations de recherche que nous souhaitons engagé dans un avenir proche ainsi que quelques réflexions sur de nouvelles voies de recherche.

Pouvoir chercher des informations sur un niveau sémantique plutôt que purement lexical devrait améliorer la recherche d'informations. Cette thèse a pour objectif de développer des modules d'analyse sémantique lexicale a n d'améliorer le système de recherche de documents textuels de la société Exalead. Les travaux présentés concernent plus spécifi quement l'analyse sémantique de texte en français. La problématique liée au traitement du français réside dans le fait qu'il n'existe que peu de ressources sémantiques et de corpus annotés pour cette langue. Rendre possible une telle analyse implique donc d'une part de pourvoir aux besoins en ressources linguistiques françaises, et d'autre part, de trouver des méthodes alternatives ne nécessitant pas de corpus français manuellement annoté. Notre manuscrit est structuré en trois parties suivies d'une conclusion. Les deux chapitres de la première partie délimitent les objectifs et le contexte de notre travail. Le premier introduit notre thèse en évoquant la problématique de la sémantique en recherche d'information, en présentant la notion de sens et en identifiant deux tâches d'analyse sémantique : la désambiguïsation lexicale et l'analyse en rôles sémantiques. Ces deux tâches font l'objet de l'ensemble de notre étude et constituent respectivement les parties 2 et 3. Le second chapitre dresse un état de l'art de toutes les thématiques abordées dans notre travail. La deuxième partie aborde le problème de la désambiguïsation lexicale. Le chapitre 3 est consacré à la constitution de nouvelles ressources françaises pour cette tâche. Nous décrivons dans un premier temps une méthode de traduction automatique des synsets nominaux de WordNet vers le français à partir de dictionnaires bilingues et d'espaces distributionnels. Puis, nous constituons une ressource automatiquement en proposant une adaptation de deux méthodes d'induction de sens existantes. L'originalité des clusters de sens ainsi constitués est de contenir des mots dont la syntaxe est proche de celle des mots source. Ces clusters sont alors exploités dans l'algorithme que nous proposons au chapitre 4 pour la désambiguïsation elle-même. Le chapitre 4 fournit également des recommandations concernant l'intégration d'un tel module dans un système de recherche de documents. L'annotation en rôles sémantiques est traitée dans la troisième partie. Suivant une structure similaire, un premier chapitre traite de la constitution de ressources pour le français, tandis que le chapitre suivant présente l'algorithme développé pour l'annotation elle-même. Ainsi, le chapitre 5 décrit nos méthodes de traduction et d'enrichissement des prédicats de FrameNet, ainsi que l'évaluation associée. Nous proposons au chapitre 6 une méthode semi-supervisée exploitant les espaces distributionnels pour l'annotation en rôles sémantiques. Nous concluons ce chapitre par une ré flexion sur l'usage des rôles sémantiques en recherche d'information et plus particulièrement dans le cadre des systèmes de réponses à des questions posées en langage naturel. La conclusion de notre mémoire résume nos contributions en soulignant le fait que chaque partie de notre travail exploite les espaces distributionnels syntaxiques et que ceci permet d'obtenir des résultats intéressants. Cette conclusion mentionne également les perspectives principales que nous inspirent ces travaux. La perspective principale et la plus immédiate est l'intégration de ces modules d'analyse sémantique dans des prototypes de recherche documentaire.