Abdendi, Moussa
(2026).
« Réductions de graphe confluentes pour l'étude du problème de l'ancrage symbolique » Thèse.
Montréal (Québec), Université du Québec à Montréal, Doctorat en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Les modèles symboliques, connexionnistes et hybrides constituent les principales approches pour modéliser le langage humain. Les modèles symboliques sont toutefois confrontés au problème de l’ancrage symbolique : un système ne peut définir les mots uniquement à partir d’autres mots sans circularité. En particulier lorsque ce type de modèle est utilisé pour modéliser des dictionnaires. Pour étudier ce phénomène, plusieurs travaux ont représenté les dictionnaires comme des graphes orientés, où le problème de l’ancrage symbolique se rapproche du problème du transversal de circuits de cardinalité minimale (TCCM), consistant à identifier un ensemble minimal de mots devant être ancrés pour briser toutes les circularités définitionnelles. Cette thèse s’inscrit dans cette lignée en apportant trois contributions principales. Tout d’abord, nous introduisons un nouveau cadre formel pour les réductions de graphes et nous rappelons notion de la confluence. Nous regroupons un ensemble de réductions utilisées dans la littérature et démontrons leur confluence, garantissant l’unicité du noyau et du graphe réduit, indépendamment de l’ordre d’application. Unicité essentielle pour garantir que les analyses et les conclusions psycholinguistiques ne dépendent pas de la stratégie de réduction suivie. Cette confluence offre également des perspectives pour des algorithmes parallèles plus rapides et adaptés aux architectures modernes des machines de calcul. Ensuite, nous présentons de nouvelles réductions d’arcs superflus et outils pour analyser les TCCMs. Nous introduisons deux nouvelles réductions polynomiales, confluentes avec l’ensemble des réductions considérées, permettant de retirer efficacement des arcs superflus sans modifier les TCCMs. Nous développons par ailleurs une nouvelle structure de données union-cat, qui conserve la trace des sommets traités par les réductions et facilite l’énumération des TCCMs dans certains cas. Enfin, nous étudions l’effet de l’application de ces réductions sur huit dictionnaires linguistiques. Nous désambiguïsons les définitions et intégrons des liens syntaxiques via des représentations abstraites du sens (RAS), produisant deux nouveaux graphes (désambiguïsé et RAS). L’application de nos réductions montre que ces enrichissements augmentent significativement la taille du noyau et du graphe réduit, tout en conservant leurs unicités et maintenant ainsi un contexte linguistique plus riche. Ces résultats démontrent que la confluence et les nouvelles réductions constituent des outils efficaces pour réduire les graphes, identifier les mots essentiels et améliorer, d’une part, la résolution du problème du TCCM et d’autre part l’étude du problème de l’ancrage symbolique.
_____________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : graphe orienté, réduction de graphe, arc superflu, problème du transversal de circuits de cardinalité minimale, problème de l’ancrage symbolique, dictionnaire
| Type: |
Thèse ou essai doctoral accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Blondin Massé, Alexandre |
| Mots-clés ou Sujets: |
Graphes orientés / Réduction de graphe / Ancrage symbolique / Transversal de circuits de cardinalité minimale / Dictionnaires de langue |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
10 févr. 2026 09:01 |
| Dernière modification: |
10 févr. 2026 09:01 |
| Adresse URL : |
https://archipel.uqam.ca/secure/id/eprint/19603 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
