Sur les systèmes de formes normales pour représenter efficacement des fonctions multivaluées

In this document, we study efficient representations, in term of size, of a given semantic content. We first extend an equational specification of median forms from the domain of Boolean functions to that of lattice polynomials over distributive lattices, both domains that are crucial in artificial intelligence. This specification is sound and complete: it allows us to algebraically simplify median forms into median normal forms (MNF), that we define as minimal median formulas with respect to a structural ordering of expressions. We investigate related complexity issues and show that the problem of deciding if a formula is in MNF, that is, minimizing the median form of a monotone Boolean function, is in sigmaP, at the second level of the polynomial hierarchy; we show that this result holds for arbitrary Boolean functions as well. We then study other normal form systems (NFSs), thought of, more generally, as a set of stratified terms over a fixed sequence of connectives, such as (m, NOT) in the case of the MNF. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as an NFS B if there is a polynomial P with nonnegative integer coefficients such that the complexity of any Boolean function f with respect to A is at most the value of P in the complexity of f with respect to B. We study monotonic NFSs, i.e., NFSs whose connectives are increasing or decreasing in each argument. We describe optimal monotonic NFSs, that are minimal with respect to the latter preorder. We show that they are all equivalent. We show that optimal monotonic NFSs are exactly those that use a single connective or one connective and the negation. Finally, we show that optimality does not depend on the arity of the connective.Dans ce document, nous étudions les représentations efficaces, en termes de taille, d'un contenu sémantique donné. Nous étendons tout d'abord une spécification équationnelle du domaine des fonctions Booléennes à celui des polynômes latticiels sur des treillis distributifs, domaines cruciaux en intelligence artificielle. Cette spécification est correcte et complète : elle nous permet de simplifier des formules médianes de manière algébrique en des formes normales médianes (MNF), que nous définissons comme des formules médianes minimales par rapport à un ordre structurel sur les expressions. Nous explorons la complexité de certaines questions connexes, et montrons que le problème qui consiste à décider si une formule est en MNF, c'est-à-dire, à simplifier la formule médiane d'une fonction Booléenne monotone, est dans sigmaP, au second niveau de la hiérarchie polynomiale : nous montrons également ce résultat pour les fonctions Booléennes arbitraires. Nous étudions ensuite d'autres systèmes de formes normales (NFSs), considérés, plus généralement, comme des ensembles de termes stratifiés selon une suite de connecteurs fixée, telle que (m, NOT) pour la MNF. Pour un NFS fixé A, la complexité d'une fonction Booléenne f par rapport à A est le minimum des tailles des termes de A qui représentent f. Cela induit un préordre sur les NFSs : un NFS A est polynomialement plus efficace qu'un NFS B s'il existe un polynôme P à coefficients entiers strictement positifs tel que la complexité de toute fonctions Booléenne f par rapport à A est majorée par la valeur de P pris en la complexité de « f » par rapport à « B ». Nous étudions les NFSs monotones, c'est-à-dire les NFSs dont les connecteurs sont croissants ou décroissants en chaque argument. Nous décrivons les NFSs monotones optimaux, qui sont minimaux par rapport au préordre ci-dessus. Nous montrons qu'ils sont tous équivalents. Nous montrons que les NFSs monotones optimaux sont exactement ceux qui ne comportent qu'un seul connecteur ou un seul connecteur et la négation. Finalement, nous montrons que l'optimalité ne dépend pas de l'arité du connecteur