@inproceedings{b26b8ba68f724fb0b491fd915af25c17,
title = "Binary decision diagrams by shared rewriting",
abstract = "In this paper we propose a uniform description of basic BDD theory and algorithms by means of term rewriting. Since a BDD is a DAG instead of a tree we need a notion of shared rewriting and develop appropriate theory. A rewriting system is presented by which canonical forms can be obtained. Various reduction strategies give rise to different algorithms. A layerwise strategy is proposed having the same time complexity as the traditional apply- algorithm, and the lazy strategy is studied, which resembles the existing up-one-algorithm. We show that these algorithms have incomparable performance.",
author = "{Pol, van de}, J.C. and H. Zantema",
year = "2000",
doi = "10.1007/3-540-44612-5_56",
language = "English",
isbn = "3-540-67901-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "609--618",
editor = "M. Nielsen and B. Rovan",
booktitle = "Mathematical Foundations of Computer Science (Proceedings 25th International Symposium, MFCS2000, Bratislava, Slovakia, August 28-September 1, 2000)",
address = "Germany",
}