1. On the efficiency of normal form systems for representing Boolean functions
- Author
-
Erkko Lehtonen, Miguel Couceiro, Romain Péchoux, Pierre Mercuriali, Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Computer Science and Communications Research Unit [Luxembourg] (CSC), Laboratory of Advanced Software SYstems [Luxembourg] (LASSY), Université du Luxembourg (Uni.lu)-Université du Luxembourg (Uni.lu), Institut für Algebra [Dresden], Technische Universität Dresden = Dresden University of Technology (TU Dresden), Designing the Future of Computational Models (MOCQUA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Polynomial ,General Computer Science ,Preorder ,Value (computer science) ,Monotonic function ,Complexity ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Arity ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Set (abstract data type) ,Integer ,Efficient representation ,Normal form system ,010201 computation theory & mathematics ,Boolean function ,0202 electrical engineering, electronic engineering, information engineering ,[INFO]Computer Science [cs] ,020201 artificial intelligence & image processing ,Mathematics - Abstract
International audience; A normal form system (NFS) for representing Boolean functions is thought of as a set of stratified terms over a fixed set of connectives. 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. In this paper we study monotonic NFSs, i.e., NFSs whose connectives are increasing or decreasing in each argument. We describe the monotonic NFSs that are optimal, i.e., that are minimal with respect to the latter preorder. We show that these minimal monotonic NFSs are all equivalent. Moreover, we address some natural questions, e.g.: does optimality depend on the arity of connectives? Does it depend on the number of connectives used? 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 connectives.
- Published
- 2020
- Full Text
- View/download PDF