Redressement

En résumé cinq réductions successives ont transformé le tableau de gauche en celui de droite :

Cette transformation a été appelée redressement par Schützenberger, et repose sur la propriété fondamentale suivante :

Théorème : le tableau redressé ne dépend pas de l'ordre des réductions.

Pour ceux et celles qui connaissent les systèmes de réécriture, les réductions forment un système confluent, et le tableau redressé (que par définition on ne peut plus réduire) est la forme normale du tableau de départ. Voici une conséquence simple de ce théorème :

Deux tableaux transformés l'un de l'autre par une suite quelconque de réductions et/ou de dilatations possèdent le même tableau redressé.

Utilisez l'animation Flash, dilatez (shift-clic) le tableau autant que vous voulez, puis réduisez-le à nouveau (alt-clic) autant que possible, et vérifiez que vous obtenez toujours le même résultat. Pendant ces expériences vous risquez de trouver les cellules vertes un peu envahissantes ; dans ce cas cliquez avec le bouton droit sur l'une d'entre elles, et choisissez Clear empty cells dans le menu déroulant.

Attention :

1. Il faut toujours cliquer sur un creux du tableau pour que la réduction ou la dilatation soient correctes. Rien n'est prévu dans l'animation Flash pour vous empêcher de cliquer sur une case qui n'est pas un creux, et les creux n'apparaissent pas automatiquement en vert : it's a feature, not a bug.
2. Seul le tableau redressé (sur lequel par définition aucune réduction n'est possible) est invariant. En particulier si vous dilatez le tableau de droite jusqu'à élimination des cinq cellules vertes, le résultat obtenu n'est pas forcément le tableau de gauche.