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.

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"
}