Locally monotone Boolean and pseudo-Boolean functions

DOI10.1016/J.DAM.2012.03.006zbMATH Open1263.06005arXiv1107.1161OpenAlexW2069599801MaRDI QIDQ444430FDOQ444430

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

Publication date: 14 August 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral properties of threshold functions
• Equivalent representations of set functions
• Axiomatizations and factorizations of Sugeno utility functions
• Title not available (Why is that?)
• Boolean calculus of differences
• Disjunctive and conjunctive normal forms of pseudo-Boolean functions
• Aggregation on finite ordinal scales by scale independent functions
• Pseudo-polynomial functions over finite distributive lattices
• Meet and Join Derivatives and Their Use in Switching Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
• Title not available (Why is that?)

Cited In (5)

• Pivotal decompositions of functions.
• The criterion of \(\tilde \alpha\)-monotonicity of Boolean functions
• Linear transformations of monotone functions on the discrete cube
• Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions
• Title not available (Why is that?)

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)