On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials

MaRDI QIDQ5144355zbMATH OpenFDO

Authors Miguel Couceiro, Pierre Mercuriali, Romain Péchoux, Abdallah Saffidine

Publication date 15 January 2021

Full work available at URL https://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-33-number-3-2019/mvlsc-33-3-p-197-218/

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An upper bound for complexity of polynomial normal forms of Boolean functions
• scientific article; zbMATH DE number 4031581
• Minimization of conjunctive normal forms of partially monotonic Boolean functions
• scientific article; zbMATH DE number 4196033
• On the efficiency of normal form systems for representing Boolean functions

Cites work

• Aczélian n-ary semigroups
• Aggregation functions.
• Characterizations of discrete Sugeno integrals as polynomial functions over distributive lattices
• Composition of Post classes and normal forms of Boolean functions
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 3235670 (Why is no real title available?)
• On the efficiency of normal form systems for representing Boolean functions
• Polyadic Groups
• Weighted lattice polynomials

Cited in

(1)

• On the efficiency of normal form systems for representing Boolean functions

Describes a project that uses

Uses Software

• JBool

This page was built for publication: On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144355)