Skip to Main content Skip to Navigation

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

Pierre Mercuriali 1
1 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : 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.
Complete list of metadata
Contributor : Thèses Ul <>
Submitted on : Tuesday, April 20, 2021 - 11:02:24 AM
Last modification on : Wednesday, April 21, 2021 - 3:33:32 AM


Files produced by the author(s)


  • HAL Id : tel-03202757, version 1


Pierre Mercuriali. Sur les systèmes de formes normales pour représenter efficacement des fonctions multivaluées. Informatique [cs]. Université de Lorraine, 2020. Français. ⟨NNT : 2020LORR0241⟩. ⟨tel-03202757⟩



Record views


Files downloads