Binary Decision Graphs

Laurent Mauborgne.
Binary Decision Graphs.
In A. Cortesi and G. Filé, editors, Static Analysis Symposium (SAS'99), volume 1694 of Lecture Notes in Computer Science, pages 101--116.
Springer-Verlag, 1999.
Compressed PostScript (105K), DVI (137K), PDF (292K).
Abstract: Binary Decision Graphs are an extension of Binary Decision Diagrams that can represent some infinite boolean functions. Three refinements of BDGs corresponding to classes of infinite functions of increasing complexity are presented. The first one is closed by intersection and union, the second one by intersection, and the last one by all boolean operations. The first two classes give rise to a canonical representation, which, when restricted to finite functions, are the classical BDDs. The paper also gives new insights in to the notion of variable names and the possibility of sharing variable names that can be of interest in the case of finite functions.

\bibitem{mauborgne99}
{\sc Mauborgne, L.}
\newblock Binary decision graphs.
\newblock In {\em Static Analyis Symposium (SAS'99)\/} (1999), A.~Cortesi and
  G.~Fil{\'e}, Eds., vol.~1694 of {\em Lecture Notes in Computer Science},
  Springer-Verlag, pp.~101--116.

@inproceedings{mauborgne99,
author = "Laurent Mauborgne",
title = "Binary Decision Graphs",
booktitle = "Static Analyis Symposium (SAS'99)",
year = 1999,
volume = 1694,
editor = "A. Cortesi and G. Fil{\'e}",
pages = "101--116",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag" }

Email: Laurent.Mauborgne@ens.fr