We are pleased to announce that we have had an article
entitled Intuitive Analysis of Certain Binary Decision Diagrams
accepted in ACM Transactions on Computational Logic.
A link to the paper and abstract are given below.
We’ll be happy to discuss the article if anyone is interested.
Kind Regards
Jim
https://www.lrde.epita.fr/dload/papers/newton.18.tocl.pdf
Abstract:
Binary Decision Diagrams (BDDs) and in particular ROBDDs (Reduced
Ordered BDDs) are a common data structure for manipulating Boolean
expressions, integrated circuit design, type inferencers, model
checkers, and many other applications. Although the ROBDD is a
lightweight data structure to implement, the behavior, in terms of
memory allocation, may not be obvious to the program architect. We
explore experimentally, numerically, and theoretically the typical
and worst-case ROBDD sizes in terms of number of nodes and residual
compression ratios, as compared to unreduced BDDs. While our
theoretical results are not surprising, as they are in keeping with
previously known results, we believe our method contributes to the
current body of research by our experimental and statistical
treatment of ROBDD sizes. In addition, we provide an algorithm to
calculate the worst-case size. Finally, we present an algorithm for
constructing a worst-case ROBDD of a given number of variables. Our
approach may be useful to projects deciding whether the ROBDD is the
appropriate data structure to use, and in building worst-case
examples to test their code.
Dear all,
I'm happy to announce the first public release of Quickref, a global
documentation project for Common Lisp.
Quickref automatically builds a website[1] containing reference manuals
for Quicklisp libraries (either those already installed or all of
them). The reference manuals are generated by Declt[2] (probably the
most complete documentation system for Lisp today) in Texinfo format,
and then processed by makeinfo. Because Declt works by introspection,
this whole process is non-intrusive: library authors do not need to do
anything to support them being documented.
The official Quickref website is kept up-to-date with Quicklisp, and
currently documents 1588 libraries successfully. This work is the result
of a collaboration with Antoine Martin, as part of an internship at
LRDE. The project is still evolving: a new student will arrive in
September to work on parallelization.
The source code is available here:
https://gitlab.common-lisp.net/quickref/quickref
The resulting website may also be regenerated locally with this Docker
2-liner:
docker run --name quickref quickref/quickref
docker cp quickref:/home/quickref/quickref .
Footnotes:
[1] http://quickref.common-lisp.net
[2] https://www.lrde.epita.fr/~didier/software/lisp/misc.php#declt
--
Resistance is futile. You will be jazzimilated.
Lisp, Jazz, Aïkido: http://www.didierverna.info
