Home – Research – Teaching

Divers

Informations générales

• Cours : INF889K, Systèmes de réécriture de termes
• Session : hiver 2026
• Groupe : 10
• Professeur : Samuele Giraudo

Plan du cours

Accessible ici.

Entente d’évaluation

Accessible ici.

Calendrier des séances

Séance 1

• Lundi 12 janvier 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : informations générales ; exemples et motivations ; systèmes de réécriture abstraits.
• Diapos : Lecture01.pdf.

Séance 2

• Lundi 19 janvier 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : propriétés des systèmes de réécriture abstraits ; terminaison ; confluence ; lemme de Newman.
• Diapos : Lecture02.pdf.

Séance 3

• Lundi 26 janvier 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : termes ; substitutions ; séries formelles.
• Diapos : Lecture03.pdf.

Séance 4

• Lundi 2 février 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : produits sur les séries formelles ; utilisation des séries formelles et des opérations pour le dénombrement ; séries en arbres et greffe.
• Diapos : Lecture04.pdf.

Séance 5

• Lundi 9 février 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : préfixes et correspondances ; systèmes de réécriture de termes ; facteurs ; formes normales et évitement de termes.
• Diapos : Lecture05.pdf.

Séance 6

• Lundi 16 février 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : relations de réduction et terminaison ; algèbres sur une signature ; méthode sémantique pour démontrer la terminaison des systèmes de réécriture de termes ; interprétations polynomiales.
• Diapos : Lecture06.pdf.

Séance 7

• Lundi 23 février 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : relations de simplification et terminaison ; relation de simplification de Knuth-Bendix ; exemples.
• Diapos : Lecture07.pdf.

Séance 8

• Lundi 9 mars 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : relations de simplification de l’ordre lexicographique sur les chemins ; unification ; algorithme de Martelli-Montanari ; chevauchement de termes ; fusion de termes.
• Diapos : Lecture08.pdf.

Séance 9

• Lundi 19 mars 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : couples critiques ; couples critiques et confluence locale ; orthogonalité ; complétion de Knuth-Bendix.
• Diapos : Lecture09.pdf.

Séance 10

• Lundi 23 mars 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : algèbres sur une signature ; variétés ; théorème HSP de Birhoff.
• Diapos : Lecture10.pdf.

Séance 11

• Lundi 30 mars 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : équivalences sémantiques et syntaxiques dans les présentations par identités ; problème du mot ; algèbres des formes normales ; clones ; clones des mots pigmentés.
• Diapos : Lecture11.pdf.

Séance 12

• Lundi 6 avril 2026, 13 h 30 à 16 h 30. Jour férié.
• Thèmes abordés : -
• Diapos : -

Séance 13

• Lundi 13 avril 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : clones libres ; présentations de clones ; algèbres sur clones ; clones et équivalence de présentations par identités ; réalisations de variétés ; règles de Tietze et équivalences de présentations par identités.
• Diapos : Lecture13.pdf.

Séance 14

• Lundi 20 avril 2026, 13 h 30 à 16 h 30.
• Thèmes abordés : paradigme de programmation par réécriture ; systèmes à constructions et fonctions ; systèmes applicatifs ; logique combinatoire.
• Diapos : Lecture14.pdf.

Séance 15

• Lundi 27 avril 2026, 13 h 30 à 16 h 30. Examen.
• Thèmes abordés : -
• Diapos : -

Cours intégral

Le cour intégral est disponible ici.

Évaluations

Document à rédiger

1. Au plus tard le 2026-02-23, envoyer à giraudo.samuele@uqam.ca une liste de trois résultats (déjà connus) dans le domaine, avec pour chacun une justification de sa pertinence (de quelques phrases à un paragraphe par résultat).

2. Au plus tard le 2026-03-09, un résultat est assigné à chaque étudiant.e.

3. Au plus tard le 2026-04-16, envoyer à giraudo.samuele@uqam.ca un document présentant le résultat assigné. Le rendu doit être rédigé en LaTeX et l’envoi doit contenir le ou les fichiers .tex et le fichier .pdf résultant. La longueur est d’entre quatre et seize pages.

La note, sur 100, est répartie comme suit :

• [25] Qualité de la démonstration du résultat et de ses composants.
• [20] Qualité de l’introduction (présentation du contexte, du résultat, ses connexions éventuelles à d’autres domaines, ses conséquences).
• [15] Qualité de la mise en œuvre de la présentation (choix de l’approche, pédagogie et clarté).
• [15] Qualité, pertinence et complétude de la bibliographie.
• [10] Pertinence des trois résultats proposés et précision de leur justification.
• [10] Qualité des exemples.
• [5] Qualité interne du code LaTeX.

À cela, s’intègrent divers malus :

• [-100] En cas de copie, complète ou partielle, de matériel existant ou engendré automatiquement.
• [-30] En cas d’une longueur vraiment en dehors de la fenêtre spécifiée.
• [-20] En cas d’erreurs manifestes d’orthographe ou de syntaxe.
• [-10] En cas d’un fort défaut dans la forme.

Présentation orale

Au plus tard le 2025-04-19, envoyer à giraudo.samuele@uqam.ca le support de présentation le cas échéant. Sinon, envoyer par courriel le fait que la présentation sera uniquement sur tableau.

Lors de la séance 14 (du 2026-04-20), il s’agit de présenter oralement (avec support) le résultat préalablement choisi.

Voici les modalités :

• la présentation se fait au tableau et/ou à l’aide d’un diaporama ;
• la durée de la présentation est de 30 minutes ;
• la présentation doit donner un bon aperçu du résultat en donnant tous les éléments pour communiquer ;
• le public cible de la présentation est un.e étudiant.e de cycle supérieur en informatique ou mathématiques n’ayant aucune connaissance particulière dans le domaine des systèmes de réécriture de termes.

La note, sur 100, est répartie comme suit :

• [30] Construction générale et plan.
• [30] Pédagogie de l’approche.
• [20] Qualité du support.
• [20] Qualité des exemples.

À cela, s’intègrent divers malus :

• [-100] En cas de copie, complète ou partielle, de matériel existant ou engendré automatiquement.
• [-30] En cas d’une durée vraiment en dehors de celle spécifiée.
• [-20] En cas d’erreurs manifestes d’orthographe ou de syntaxe.
• [-10] En cas d’un fort défaut dans la forme.

Examen

L’examen aura lieu le 2026-04-27 en lieu et place de la dernière séance de cours. Il contiendra des questions d’application du cours (par exemple, démontrer qu’un système de réécriture de termes donné est terminant et/ou confluent) et des questions plus abstraites (par exemple, des questions sur des propriétés générales de certains systèmes de réécriture). Il pourra aussi y avoir des questions de nature combinatoire, dans le style de ce qui est proposé dans les chapitres sur les termes et les séries formelles (par exemple, de décrire la série caractéristique des termes qui évitent un certain ensemble de motifs).