Show simple item record

dc.contributor.authorCouceiro, M.
dc.contributor.authorMercuriali, Pierre
dc.contributor.authorPéchoux, Romain
dc.contributor.authorSaffidine, Abdallah
dc.date.accessioned2020-09-29T15:00:06Z
dc.date.available2020-09-29T15:00:06Z
dc.date.issued2019
dc.identifier.issn1542-3980
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21005
dc.language.isoenen
dc.subjectEfficient representation
dc.subjectComplexity
dc.subjectNormal form
dc.subjectBoolean function
dc.subjectLattice polynomial
dc.subject.ddc511en
dc.titleOn the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this document, we consider a median-based calculus to represent monotone Boolean functions efficiently. We study an equational specification of median forms and extend it from the domain of monotone Boolean functions to the domain of polynomial functions over distributive lattices. This specification is sound and complete. We illustrate its usefulness when simplifying median formulas algebraically. Furthermore, we propose a definition of median normal forms (MNF), that are thought of as minimal median formulas with respect to a structural ordering of expressions. We investigate related complexity issues and show that the problem of deciding whether a formula is in MNF, that is the problem of minimizing the median form of a monotone Boolean function, is in ∑P2. Moreover, we show that it still holds for arbitrary Boolean functions, not necessarily monotone.
dc.relation.isversionofjnlnameJournal of Multiple-Valued Logic and Soft Computing
dc.relation.isversionofjnlvol33
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2019
dc.relation.isversionofjnlpages197-218
dc.identifier.urlsitehttps://hal.inria.fr/hal-01905491
dc.relation.isversionofjnlpublisherOCP Science
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingouien
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2020-09-30T10:55:52Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record