Pseudo-Boolean Constraints from a Knowledge Representation Perspective

Daniel Le Berre, Pierre Marquis, Stefan Mengel, Romain Wallon

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

Main track. Pages 1891-1897.

Abstract

We study pseudo-Boolean constraints (PBC) and

their special case cardinality constraints (CARD)

from the perspective of knowledge representation.

To this end, the succinctness of PBC and CARD

is compared to that of many standard propositional

languages. Moreover, we determine which queries

and transformations are feasible in polynomial time

when knowledge is represented by PBC or CARD,

and which are not (unconditionally or unless P =

NP). In particular, the advantages and disadvantages

compared to CNF are discussed.

Knowledge Representation and Reasoning: Knowledge Representation Languages
Constraints and SAT: Constraints and SAT
Knowledge Representation and Reasoning: Tractable Languages and Knowledge compilation