Définitions

Champ de données :

Soit V un multi-ensemble de valeurs. Soit v une fonction de Zⁿ dans V et  une bijection de Zⁿ dans Z^p, alors la paire (v : ) définit un champ de données si dom(v) est inclus dans dom().

Soient deux champs de données X et Y. X et Y sont dits faiblement équivalents si et seulement si ils représentent un même multi-ensemble de valeurs.

Equivalence forte

Soient deux champs de données X et Y. X et Y sont dits fortement équivalents si et seulement si il existe une bijection h telle que Y = h :: X et dom(_X) est inclus dans dom(h).

Programme PEI :

Un énoncé PEI est un programme si, pour tout jeu de champs de données en entrée, il existe au plus un ensemble de champs de données en sortie définissant une solution du système d'équations.
Cette définition a pour conséquence de ne pas considérer comme des programmes les énoncés ayant des résultats non déterministes.

Pré-équation

Une pré-équation d'un énoncé P est une équation liant uniquement des champs de données en entrées de P.

Post-équation

Une équation d'un énoncé P est une post-équation si elle n'est pas un pré-équation.

Superposition :

Un opérateur interne de superposition, noté /&/ est défini en PEI. La superposition de plusieurs champs de données permet d'en définir un nouveau dont les valeurs sont des séquences. Chaque séquence est la concaténation des valeurs des champs placés aux mêmes indices dans le référentiel.
 

4 7 5 X

4 5 0 4 W

4;4 7;5 5;0 4 Z = X /&/ W

 

Notation des opérations

La notation des opérations est dérivée du lambda-calcul. Une fonction f de domaine {x| P(x)} est notée par l'expression (x)|P(x).f(x). Par commodité, il est possible d'écrire (x).f(x) au lieu de (x)|true.f(x) et (x)|P(x) au lieu de (x)|P(x).(x).

Une fonction f notée sur des sous-domaines disjoints est notée f1#f2. Le mot-clé id est utilisé pour filtrer les séquences à un élément.

Une fonction peut apparaître directement dans l'expression de champs de données ou bien être référencée par un nom de fonction dont la définition est reportée en dehors du système d'équations.