On the error resilience of ordered binary decision diagrams
An Ordered Binary Decision Diagram (OBDD) is a data structure that is used in an increasing number of fields of Computer Science (e.g., logic synthe- sis, program verification, data mining, bioinformatics, and data protection) for representing and manipulating discrete structures and Boolean functio...
Published in: | Theoretical Computer Science |
---|---|
Main Authors: | , , |
Other Authors: | |
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
2015
|
Subjects: | |
Online Access: | http://hdl.handle.net/11568/750039 https://doi.org/10.1016/j.tcs.2015.05.050 http://www.sciencedirect.com/science/article/pii/S0304397515005149 |
id |
ftunivpisairis:oai:arpi.unipi.it:11568/750039 |
---|---|
record_format |
openpolar |
spelling |
ftunivpisairis:oai:arpi.unipi.it:11568/750039 2024-02-27T08:45:53+00:00 On the error resilience of ordered binary decision diagrams BERNASCONI, ANNA Ciriani, Valentina Lago, Lorenzo Bernasconi, Anna Ciriani, Valentina Lago, Lorenzo 2015 STAMPA http://hdl.handle.net/11568/750039 https://doi.org/10.1016/j.tcs.2015.05.050 http://www.sciencedirect.com/science/article/pii/S0304397515005149 eng eng info:eu-repo/semantics/altIdentifier/wos/WOS:000358460200002 volume:595 firstpage:11 lastpage:33 numberofpages:23 journal:THEORETICAL COMPUTER SCIENCE http://hdl.handle.net/11568/750039 doi:10.1016/j.tcs.2015.05.050 info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-84937418728 http://www.sciencedirect.com/science/article/pii/S0304397515005149 info:eu-repo/semantics/openAccess info:eu-repo/semantics/article 2015 ftunivpisairis https://doi.org/10.1016/j.tcs.2015.05.050 2024-01-31T17:45:40Z An Ordered Binary Decision Diagram (OBDD) is a data structure that is used in an increasing number of fields of Computer Science (e.g., logic synthe- sis, program verification, data mining, bioinformatics, and data protection) for representing and manipulating discrete structures and Boolean functions. The purpose of this paper is to study the error resilience of OBDDs and to design a resilient version of this data structure, i.e., a self-repairing OBDD. In particular, we describe some strategies that make reduced ordered OBDDs resilient to errors in the indices, that are associated to the input variables, or in the pointers (i.e., OBDD edges) of the nodes. These strategies exploit the inherent redundancy of the data structure, as well as the redundancy introduced by its efficient implementations. The solutions we propose allow the exact restoring of the original OBDD and are suitable to be applied to classical software packages for the manipulation of OBDDs currently in use. Another result of the paper is the definition of a new canonical OBDD model, called Index-Resilient Reduced OBDD, which guarantees that a node with a faulty index has a reconstruction cost O(r), where r is the number of nodes with corrupted index. Experimental results on a classical benchmark suite validate the proposed approaches. Article in Journal/Newspaper The Pointers ARPI - Archivio della Ricerca dell'Università di Pisa Theoretical Computer Science 595 11 33 |
institution |
Open Polar |
collection |
ARPI - Archivio della Ricerca dell'Università di Pisa |
op_collection_id |
ftunivpisairis |
language |
English |
description |
An Ordered Binary Decision Diagram (OBDD) is a data structure that is used in an increasing number of fields of Computer Science (e.g., logic synthe- sis, program verification, data mining, bioinformatics, and data protection) for representing and manipulating discrete structures and Boolean functions. The purpose of this paper is to study the error resilience of OBDDs and to design a resilient version of this data structure, i.e., a self-repairing OBDD. In particular, we describe some strategies that make reduced ordered OBDDs resilient to errors in the indices, that are associated to the input variables, or in the pointers (i.e., OBDD edges) of the nodes. These strategies exploit the inherent redundancy of the data structure, as well as the redundancy introduced by its efficient implementations. The solutions we propose allow the exact restoring of the original OBDD and are suitable to be applied to classical software packages for the manipulation of OBDDs currently in use. Another result of the paper is the definition of a new canonical OBDD model, called Index-Resilient Reduced OBDD, which guarantees that a node with a faulty index has a reconstruction cost O(r), where r is the number of nodes with corrupted index. Experimental results on a classical benchmark suite validate the proposed approaches. |
author2 |
Bernasconi, Anna Ciriani, Valentina Lago, Lorenzo |
format |
Article in Journal/Newspaper |
author |
BERNASCONI, ANNA Ciriani, Valentina Lago, Lorenzo |
spellingShingle |
BERNASCONI, ANNA Ciriani, Valentina Lago, Lorenzo On the error resilience of ordered binary decision diagrams |
author_facet |
BERNASCONI, ANNA Ciriani, Valentina Lago, Lorenzo |
author_sort |
BERNASCONI, ANNA |
title |
On the error resilience of ordered binary decision diagrams |
title_short |
On the error resilience of ordered binary decision diagrams |
title_full |
On the error resilience of ordered binary decision diagrams |
title_fullStr |
On the error resilience of ordered binary decision diagrams |
title_full_unstemmed |
On the error resilience of ordered binary decision diagrams |
title_sort |
on the error resilience of ordered binary decision diagrams |
publishDate |
2015 |
url |
http://hdl.handle.net/11568/750039 https://doi.org/10.1016/j.tcs.2015.05.050 http://www.sciencedirect.com/science/article/pii/S0304397515005149 |
genre |
The Pointers |
genre_facet |
The Pointers |
op_relation |
info:eu-repo/semantics/altIdentifier/wos/WOS:000358460200002 volume:595 firstpage:11 lastpage:33 numberofpages:23 journal:THEORETICAL COMPUTER SCIENCE http://hdl.handle.net/11568/750039 doi:10.1016/j.tcs.2015.05.050 info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-84937418728 http://www.sciencedirect.com/science/article/pii/S0304397515005149 |
op_rights |
info:eu-repo/semantics/openAccess |
op_doi |
https://doi.org/10.1016/j.tcs.2015.05.050 |
container_title |
Theoretical Computer Science |
container_volume |
595 |
container_start_page |
11 |
op_container_end_page |
33 |
_version_ |
1792055272001241088 |