No full text
Article (Scientific journals)
Locally monotone Boolean and pseudo-Boolean functions
Couceiro, Miguel; Marichal, Jean-Luc; Waldhauser, Tamás
2012In Discrete Applied Mathematics, 160 (12), p. 1651-1660
Peer reviewed
 

Files


Full Text
No document available.
Full Text Parts
LocallyMonotoneBPBF.pdf
Author postprint (151.29 kB)
Download
PV-LocallyMonotoneBPBF.pdf
Publisher postprint (259.57 kB)
Request a copy

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Boolean function; Pseudo-Boolean function; Local monotonicity; Discrete partial derivative; Join and meet derivatives
Abstract :
[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.
Disciplines :
Mathematics
Electrical & electronics engineering
Identifiers :
UNILU:UL-ARTICLE-2012-486
Author, co-author :
Couceiro, Miguel ;  University Paris-Dauphine, Paris, France > Lamsade
Marichal, Jean-Luc ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit
Waldhauser, Tamás ;  University of Szeged, Szeged, Hungary > Bolyai Institute
Language :
English
Title :
Locally monotone Boolean and pseudo-Boolean functions
Publication date :
August 2012
Journal title :
Discrete Applied Mathematics
ISSN :
0166-218X
Publisher :
Elsevier Science, Amsterdam, Netherlands
Special issue title :
Special Section: Boolean and Pseudo-Boolean Functions
Volume :
160
Issue :
12
Pages :
1651-1660
Peer reviewed :
Peer reviewed
Name of the research project :
F1R-MTH-PUL-12RDO2 > MRDO2 > 01/02/2012 - 31/01/2015 > MARICHAL Jean-Luc
Funders :
University of Luxembourg - UL
Available on ORBilu :
since 26 October 2013

Statistics


Number of views
78 (5 by Unilu)
Number of downloads
119 (1 by Unilu)

Scopus citations®
 
2
Scopus citations®
without self-citations
1
OpenCitations
 
2
WoS citations
 
1

Bibliography


Similar publications



Contact ORBilu