This paper discusses the error resilience of Zero-Suppressed Binary Decision Diagrams (ZDDs), which are a particular family of Ordered Binary Decision Diagrams used for representing and manipulating combination sets. More precisely, we design a new ZDD canonical form, called index-resilient reduced ZDD, such that a faulty index can be reconstructed in time O(k), where k is the number of nodes with a corrupted index.
Zero-suppressed binary decision diagrams resilient to index faults / A. Bernasconi, V. Ciriani - In: Theoretical computer science : 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014, Rome, Italy, september 1-3, 2014 : proceedings / [a cura di] J. Diaz, I. Lanese, D. Sangiorgi. - Berlin : Springer, 2014. - ISBN 9783662446010. - pp. 1-12 (( Intervento presentato al 8. convegno IFIP TC 1/WG 2.2 International Conference, TCS 2014 tenutosi a Roma nel 2014 [10.1007/978-3-662-44602-7_1].
Zero-suppressed binary decision diagrams resilient to index faults
V. Ciriani
2014
Abstract
This paper discusses the error resilience of Zero-Suppressed Binary Decision Diagrams (ZDDs), which are a particular family of Ordered Binary Decision Diagrams used for representing and manipulating combination sets. More precisely, we design a new ZDD canonical form, called index-resilient reduced ZDD, such that a faulty index can be reconstructed in time O(k), where k is the number of nodes with a corrupted index.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
