Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 1

available in:   PDF (157 kB) PS (56 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-01-0097


Monotone, Horn and Quadratic Pseudo-Boolean Functions

Stephan Foldes (RUTCOR, Rutgers University, USA)

Peter L. Hammer (RUTCOR, Rutgers University, USA)

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: Binary optimization, Boolean functions, Horn functions, Set functions, Truth functions, pseudo-Boolean functions

Categories: F.4, G.2