Systèmes de réécriture et le problème du mot dans un monoïde

الموضوعات

رياضة

الملخص

Notre recherche dans cette thèse se situe dans le cadre de semi-systèmes de réécriture ditaussi semi-système de Thue et le problème du mot dans un monoïde. Un semi-système deréécriture est un couple ( ;R) où est un alphabet et R est un ensemble ni de couples demots sur , i.e, R où est le monoïde libre engendré par muni de l opérationla concaténation des mots.L étude des propriétés des semi-systèmes de réécriture forme un domaine très importantdepuis de nombreuses années. Parmi les propriétés les plus étudiées et les plus importantesdes semi-systèmes de réécriture se trouvent la terminaison qui assure l existence d un résultatà un calcul et la con uence qui nous permet de garantir l unicité de ce résultat.Dans ce travail on donne des critères pour assurer la propriété de terminaison dans les deuxcas suivants:Dans le premier cas, on utilise un morphisme non contractant entre le semi-système ( ;R)en question et un autre semi-système possédant déjà cette propriété. Dans le second cas,on utilise une fonction poids entre le semi-système ( ;R) et un ensemble muni d un ordrebien fondé.Soit ( ;R) un semi-système de réécriture. La congruence ()Rengendrée par R est dé niepar: w()Rw0, s il existe x; y de et (r; s) 2 (R [ R&###1048576;1) tels que w = xry et w0 = xsy, w ()Rw0 , s il existe une suite nie de mots u0; u1; :::; un de avec,u0 = w; ui()Rui+1; 80 i n &###1048576; 1 et un = w0.Une présentation (par générateurs et relations) d un monoïde M est la donnée d unalphabet et d une relation binaire R sur tels que M soit isomorphe au quotient depar la congruence notée ()Rengendré par R, i.e, M = = ()R.Etants données deux semi-systèmes de réecriture ( 1;R1) et ( 2;R2). Nous avons déter-miné quelques conditions sur les relations R1 et R2 qui permettent d assurer l existence d unmorphisme entre les monoïdes 1= () R1et 2= () R2pour assurer le passage entre les deuximonoïdes quotients. D autre part, on donne une relation spéci que R sur qui fait dumonoïde quotient = ()Run groupe.Le problème du mot dans un monoïde libre qu on peut formuler comme suit : Etantdonnés le semi-système de réécriture ( ;R) et les deux mots w;w0 de , déterminer sion peut dériver w0 à partir de w en utilisant la congruence engendré par R, c est-à-direw ()Rw0. Ce problème est connu qu il est en général indécidable.En n, on s intéresse au protocole ATS-monoïde , l idée de ce protocole est de transformerun semi-système de Thue ( ;R) pour lequel le problème du mot est indécidable en un semi-système de Thue ( ;R ) où pour lequel le problème du mot est décidable entemps linéaire. Plus précisément, on donne des attaques contre ATS-monoïde dans des casspéci ques et quelques exemples sur ces cas.

روابط وملفات

التعريف والنوع

رقم الوثيقة

f58ad226-c811-48d5-84a3-2a05cc966f66

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل دكتوراة

نوع الملف

pdf text

أسماء الملفات

191986_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":"Douadi Mihoubi ","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Nacer Ghadbane","title_ar":"اعداد","title_en":"Preparation"}]

اللغة

French

المصدر والدورية

اسم المصدر

Systèmes de réécriture et le problème du mot dans un monoïde

المحتوى والصفحات

عدد الصفحات

0

إشراف وإعداد

الإشراف

Douadi Mihoubi

الإعداد

Nacer Ghadbane

الاقتباسات الببليوغرافية