Skip to Main content Skip to Navigation
Conference papers

Normal form systems generated by single connectives have mutually equivalent efficiency

Miguel Couceiro 1 Erkko Lehtonen 2 Pierre Mercuriali 3 Romain Péchoux 3 Mathias Soeken 4
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
3 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this paper we consider a Normal Form System (NFS) as being a factorization of the class of all Boolean functions into a composition of clones. This formalism includes classical normal forms such as DNF, CNF,. .. We study the efficiency of NFSs that yield terms built using one or several connectives taken in a fixed order, and applied to literals and constants. Here, efficiency is measured by the minimal size of terms representing a function. Each clone is finitely generated but can have different sets of generators. We show that the choice of the generator used in a given NFS does not impact its efficiency, up to polynomial equivalence.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Romain Péchoux Connect in order to contact the contributor
Submitted on : Thursday, March 5, 2020 - 11:07:12 AM
Last modification on : Friday, January 21, 2022 - 3:23:02 AM
Long-term archiving on: : Saturday, June 6, 2020 - 1:35:02 PM


Files produced by the author(s)



Miguel Couceiro, Erkko Lehtonen, Pierre Mercuriali, Romain Péchoux, Mathias Soeken. Normal form systems generated by single connectives have mutually equivalent efficiency. DICE 2018 - Developments in Implicit Computational Complexity, Apr 2018, Thessaloniki, Greece. ⟨10.4230/LIPIcs.DICE.2016.1⟩. ⟨hal-02499377⟩



Les métriques sont temporairement indisponibles