Normal form systems generated by single connectives have mutually equivalent efficiency - Archive ouverte HAL Access content directly
Conference Papers Year :

Normal form systems generated by single connectives have mutually equivalent efficiency

(1) , (2) , (3) , (3) , (4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
DICE_2018_paper_7.pdf (360.25 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02499377 , version 1 (05-03-2020)

Identifiers

Cite

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⟩
26 View
21 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More