JUCS - Journal of Universal Computer Science 6(1): 97-104, doi: 10.3217/jucs-006-01-0097
Monotone, Horn and Quadratic Pseudo-Boolean Functions
expand article infoStephan Foldes‡, Peter L. Hammer‡
‡ RUTCOR, Rutgers University, Piscataway, United States of America

Corresponding author: Stephan Foldes ( sfoldes@rutcor.rutgers.edu )

© Stephan Foldes, Peter Hammer.
This article is freely available under the J.UCS Open Content License.
Citation: Foldes S, Hammer PL (2000) Monotone, Horn and Quadratic Pseudo-Boolean Functions. JUCS - Journal of Universal Computer Science 6(1): 97-104. https://doi.org/10.3217/jucs-006-01-0097
Open Access
Abstract
A pseudo-Boolean function (pBf) is a mapping from {0,1}^n to the real numbers. It is known that pseudo-Boolean functions have polynomial representations, and it was recently shown that they also have disjunctive normal forms (DNFs). In this paper we relate the DNF syntax of the classes of monotone, quadratic and Horn pBfs to their characteristic inequalities. 1 C.S.Calude and G.Stefanescu (eds.). Automata, Logic, and Computability. Special issue dedicated to Professor Sergiu Rudeanu Festschrift.
Keywords
pseudo-Boolean functions, Set functions, Boolean functions, Truth functions, Horn functions, Binary optimization