Translation among CNFs, characteristic models and ordered binary decision diagrams
✍ Scribed by Takashi Horiyama; Toshihide Ibaraki
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 118 KB
- Volume
- 85
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their Horn CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results hold on any class of functions having a basis of polynomial size.