Reference : Locally monotone Boolean and pseudo-Boolean functions
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Electrical & electronics engineering
http://hdl.handle.net/10993/9474
Locally monotone Boolean and pseudo-Boolean functions
English
Couceiro, Miguel mailto [University Paris-Dauphine, Paris, France > Lamsade]
Marichal, Jean-Luc mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
Waldhauser, Tamás mailto [University of Szeged, Szeged, Hungary > Bolyai Institute]
Aug-2012
Discrete Applied Mathematics
Elsevier Science
160
12
Special Section: Boolean and Pseudo-Boolean Functions
1651-1660
Yes
International
0166-218X
Amsterdam
The Netherlands
[en] Boolean function ; Pseudo-Boolean function ; Local monotonicity ; Discrete partial derivative ; Join and meet derivatives
[en] We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p=2.
University of Luxembourg - UL
Researchers ; Professionals ; Students
http://hdl.handle.net/10993/9474
10.1016/j.dam.2012.03.006
http://arxiv.org/abs/1107.1161

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
LocallyMonotoneBPBF.pdfAuthor postprint147.75 kBView/Open
Limited access
PV-LocallyMonotoneBPBF.pdfPublisher postprint253.48 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.