Antichaîne

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En mathématiques, plus précisément en théorie des ordres, une antichaîne d'un ensemble E muni d'une relation d'ordre (notée ici ≤ ) est une partie A de E telle que, pour tout x, y de A,

Autrement dit, dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables.

La largeur d'un ordre est le maximum des cardinaux de ses antichaînes (par exemple : un ordre total sur un ensemble non vide est un ordre de largeur 1).

Antichaînes de ℕ[modifier | modifier le code]

Considérons l'ensemble N des entiers naturels, ordonné par la divisibilité.

Pour tout entier naturel n, la largeur de {1, 2… , 2n} (muni de l'ordre induit) est n. De plus, dans cet ensemble ordonné, un élément de la forme 2kc avec c impair appartient à une antichaîne maximale (i.e. de cardinal n) si et seulement si 2n < 3k + 1 c.

Applications en informatique[modifier | modifier le code]

Les antichaînes sont utilisées en informatique comme une structure de données efficace en model checking [1],[2].

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Antichain », MathWorld

Références[modifier | modifier le code]

  1. (en) M. De Wulf, L. Doyen, N. Maquet et J.-F. Raskin, « Antichains: Alternative Algorithms for LTL Satisfiability and Model-Checking », Tools and Algorithms for the Construction and Analysis of Systems, Springer, Berlin, Heidelberg, série Lecture Notes in Computer Science,‎ , p. 63–77 (ISBN 9783540787990, DOI 10.1007/978-3-540-78800-3_6, lire en ligne)
  2. (en) « Antichains »