cl-banner

Size Complexity of BDD Construction of Pseudo-Boolean Constraints in Binary/Mixed-Radix Base Form

Naoki Nagatsuka, Masahiko Sakai, Harald Zankl, and Keiichirou Kusakari

Proceedings of the 28th Annual Conference of the Japan Society of Artificial Intelligence (JSAI 2014), ID4-OS-11a-3, 2014.

Abstract

An ROBDD with ascending variable order representing a Pseudo-Boolean constraint has polynomial size if all coefficients in the constraint are powers of two (Abio et al. 2012). This paper extends the result to descending variable-orders and generalizes it to Pseudo-Boolean constraints having mixed-radix base coefficients (for ascending and descending variable-orders). We implemented the proposed constructions and report on experimental results.

 

  PDF

BibTeX 

@inproceedings{NNMSHZKK-JSAI14,
author = "Naoki Nagatsuka and Masahiko Sakai and Harald Zankl and Keiichirou Kusakari",
title = "Size Complexity of BDD Construction of Pseudo-Boolean
Constraints in Binary/Mixed-Radix Base Form",
booktitle = "Proceedings of the 28th Annual Conference of the Japan Society of
Artifical Intelligence",
number = "1D4-OS-11a-3",
year = 2014,
note = "4 pages"
}
Nach oben scrollen