Publikationen

2006

A Purely Functional Implementation of ROBDDs in Haskell

Christiansen, J. ., & Huch, F. . (2006). A Purely Functional Implementation of ROBDDs in Haskell. Trends in Functional Programming, 7, 55–71.

Abstract

This paper presents an implementation of the ROBDD data structure in Haskell. It shows that lazy evaluation can be used to improve the performance of some ROBDD algorithms. While standard implementations construct the whole structure no matter which parts are demanded we use lazy evaluation to provide a more demand driven construction. To achieve this behavior we have to relax a property that guarantees that ROBDDs contain no redundant nodes. All measurements show that relaxing causes only a small number of additional nodes. Furthermore we present an equality check implementation that performs well although it does not make use of canoicity. The canonicity is lost because of the relaxing. The equality check implementation benefits highly from laziness.

2006

A Purely Functional Implementation of ROBDDs in Haskell

Abstract

Exportformate

Weiterführende Links

Filter Tags

2004

Searching for Deadlocks While Debugging Concurrent Haskell Programs

Exportformate

Weiterführende Links

Filter Tags