Pseudo-Boolean Constraints from a Knowledge Representation Perspective

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.

Authors

• Daniel Le Berre
• Pierre Marquis Univ. Artois, CNRS, CRIL, Lens, France Institut Universitaire de France
• Stefan Mengel University of Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL)
• Romain Wallon a:1:{s:5:"en_US";s:24:"CRIL, Univ Artois & CNRS";}

Keywords

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