Un ensemble d'opérations finies sur un ensemble fixé qui contient toutes les fonctions de projection et est fermé par composition (substitution d'opérations dans les arguments).

Principe

La fermeture par composition combinée à la présence des projections caractérise l'idée algébrique de toutes les opérations terme définissables à partir d'un signe ou d'une algèbre donnée ; les clones captent l'essence opérationnelle de la puissance expressive d'une algèbre.

Démonstration

Sur l'ensemble à deux éléments {0,1}, l'ensemble de toutes les fonctions booléennes (de toutes arités finies) forme un clone ; les sous-ensembles fermés par composition et contenant les projections correspondent aux clones classiques de la structure de Post, comme le clone des fonctions booléennes monotones.

Mauvaise application

Qualifier de clone tout ensemble de fonctions fermé par combinaison point par point, ou confondre clones et groupes de permutations ; ces erreurs ignorent les projections requises et la fermeture compositionnelle qui définissent les clones.

Conséquence

Connaître le clone d'opérations détermine quelles relations sont préservées (polymorphismes) et classe ainsi la définissabilité et les propriétés computationnelles (par exemple, la complexité des problèmes de satisfaction de contraintes dépend des clones de polymorphismes).

Inversion

La perspective duale porte sur des ensembles de relations fermés par définitions primitives positives (co-clones) ; inverser le point de vue des opérations vers les relations fournit des outils de classification complémentaires et des invariants techniques différents.

Limite

Ne concerne que les opérations finies (à arité finie) sur un même ensemble support et exige toutes les projections ; exclut les opérations infinies en arité, les sorties multiples et les collections dépourvues de projections.

Tension sémantique

Le concept de Clone est en tension avec celui de monoïde d'opérations ou d'algèbre engendrée : un clone met l'accent sur la fermeture par composition arbitraire et les projections, tandis qu'une algèbre engendrée peut viser la fermeture sous opérations primitives spécifiques, ce qui change la notion de définissabilité.

Synthèse

Un Clone est l'ensemble complet des opérations terme finies sur un ensemble donné, fermé par composition et contenant les projections ; il synthétise la puissance opérationnelle d'une algèbre et relie de façon centrale opérations et relations préservées.