IBP-Litp-1995/Th/04

Rangs des relations binaires Semigroupes de relations non ambigus

V. FROIDURE

IBP-Litp 1995/Th/04: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
134 pages - Novembre/November 1995 - French document.

PostScript : Ko /Kb

Titre / Title: Rangs des relations binaires Semigroupes de relations non ambigus

Résumé : Dans cette thèse, nous étudions différentes notions de rang d'une relation binaire. Nous avons retenu trois notions de rang qui s'avèrent intéressantes dans le cadre des monoïdes de relations et des monoïdes de relations non ambigus, et une quatrième notion un peu différente, appelée "grade" d'une relation.
La première partie du travail consiste à comparer systématiquement les rangs entre eux. Nous poursuivons l'étude de cas pour les rangs maximaux et nous calculons les valeurs interdites du grade. Dans chaque cas, nous étudions le cas général puis le cas des relations non ambiguës.
Dans la deuxième partie, nous étudions le comportement des rangs dans des semigroupes de relations. Nous montrons d'abord l'égalité des rangs des relations régulières dans les semigroupes de relations non ambigus. La question de l'égalité des rangs des relations non régulières est résolue grâce à plusieurs contre-exemples, en particulier dans les monoïdes de relations non ambigus transitifs.
Dans la troisième partie, nous étudions la complexité du calcul des rangs et présentons divers algorithmes liés au calcul du rang.
La thèse est complétée par des annexes contenant plusieurs modules, écrits en C et en Pascal que nous avons développés pour compléter des programmes existants (AMORE) et mener à bien des calculs expérimentaux pour tester nos conjectures.

Abstract : In this thesis, various notions of rank of a binary relation are studied. Three of these notions are interesting within the context of monoids of relations and unambiguous monoids of relations, and a fourth one, called the "grade" of a relation, is of a different nature.
The first part consists in comparing systematically the ranks between them. We go on with the study of maximal ranks and we compute forbidden values of the grade. In each case, we study the general case, and then, the case of unambiguous relations.
The second part is a study of ranks in semigroups of relations. We show the equality of ranks for regular relations in unambiguous semigroups. Then, the question of equality of ranks for non regular relations is answered thanks to several counter-examples.
In the third part, we present some algorithms for computing the rank and we analyze them.
The thesis is completed by several program units written in C and Pascal that we developped in order to complete existing programs (AMORE) and achieve experimental computations to test our conjectures.

Publications internes Litp 1995 / Litp research reports 1995