Pseudo-Boolean Constraints from a Knowledge Representation Perspective
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.
Cite
Text
Le Berre et al. "Pseudo-Boolean Constraints from a Knowledge Representation Perspective." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/261Markdown
[Le Berre et al. "Pseudo-Boolean Constraints from a Knowledge Representation Perspective." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/berre2018ijcai-pseudo/) doi:10.24963/IJCAI.2018/261BibTeX
@inproceedings{berre2018ijcai-pseudo,
title = {{Pseudo-Boolean Constraints from a Knowledge Representation Perspective}},
author = {Le Berre, Daniel and Marquis, Pierre and Mengel, Stefan and Wallon, Romain},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {1891-1897},
doi = {10.24963/IJCAI.2018/261},
url = {https://mlanthology.org/ijcai/2018/berre2018ijcai-pseudo/}
}