Infinitary relations and their representation

Laurent Mauborgne.
Infinitary relations and their representation.
Science of Computer Prgramming, 47:121--144, 2003
Compressed PostScript (218K), DVI (172K), PDF (246K).
Abstract: This papers presents extensions of Binary Decision Diagrams to represent some infinitary relations (coded as infinite boolean functions). Four classes of infinitary relations are presented, and their representations are discussed. The widest class is closed under all boolean operations. The three others give rise to a canonical representation, which, when restricted to finite relations, are the classical BDDs. The paper also gives new insights in to the notion of variables and the possibility of sharing variables that can be of interest in the case of finite relations.

\bibitem{mauborgne03}
{\sc Mauborgne, L.}
\newblock Infinitary relations and their representation.
\newblock {\em Science of Computer Programming 47}, (2003), 121--144.

@article{mauborgne03,
author = "Laurent Mauborgne",
title  = "Infinitary relations and their representation",
journal = "Science of Computer Programming",
year   = 2003,
volume = 47,
pages  = "121--144"}

Email: Laurent.Mauborgne@ens.fr