Locally monotone Boolean and pseudo-Boolean functions

DOI10.1016/J.DAM.2012.03.006MaRDI QIDQ444430zbMATH OpenOpenAlexFDO

Authors Miguel Couceiro, Jean-Luc Marichal, Tamás Waldhauser

Publication date 14 August 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1161

zbMATH Keywords

Boolean functionpseudo-Boolean functionlocal monotonicitydiscrete partial derivativejoin and meet derivatives

Mathematics Subject Classification ID

Game theory (91A99) Boolean programming (90C09) Boolean functions (06E30)

Abstract: 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.

Recommendations

• Algebraic and topological closure conditions for classes of pseudo-Boolean functions
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
• scientific article; zbMATH DE number 3984974
• scientific article; zbMATH DE number 1543344
• Monotone Boolean functions

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3599956 (Why is no real title available?)
• scientific article; zbMATH DE number 1507346 (Why is no real title available?)
• scientific article; zbMATH DE number 3440322 (Why is no real title available?)
• scientific article; zbMATH DE number 3246292 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• scientific article; zbMATH DE number 3269066 (Why is no real title available?)
• scientific article; zbMATH DE number 2233860 (Why is no real title available?)
• Aggregation on finite ordinal scales by scale independent functions
• Axiomatizations and factorizations of Sugeno utility functions
• Boolean calculus of differences
• Disjunctive and conjunctive normal forms of pseudo-Boolean functions
• Equivalent representations of set functions
• Meet and Join Derivatives and Their Use in Switching Theory
• Pseudo-polynomial functions over finite distributive lattices
• Spectral properties of threshold functions
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions

Cited in

(5)

• The criterion of \(\tilde \alpha\)-monotonicity of Boolean functions
• Linear transformations of monotone functions on the discrete cube
• Pivotal decompositions of functions.
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
• scientific article; zbMATH DE number 3979131 (Why is no real title available?)

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Locally monotone Boolean and pseudo-Boolean functions

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