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 metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-02499377
Contributor : Romain Péchoux <>
Submitted on : Thursday, March 5, 2020 - 11:07:12 AM
Last modification on : Thursday, March 5, 2020 - 7:01:05 PM
Document(s) archivé(s) le : Saturday, June 6, 2020 - 1:35:02 PM

File

DICE_2018_paper_7.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

31

Files downloads

40