Compressing Binary Decision Diagrams

Esben Rune Hansen; Srinivasa Rao Satti; Peter Tiedemann

Compressing Binary Decision Diagrams

Esben Rune Hansen, Srinivasa Rao Satti, Peter Tiedemann

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

Abstract

The paper introduces a new technique for compressing Binary Decision Diagrams in those cases where random access is not required. Using this technique, compression and decompression can be done in linear time in the size of the BDD and compression will in many cases reduce the size of the BDD to 1-2 bits per node.
Empirical results for our compression technique are presented, including comparisons with previously introduced techniques, showing that the new technique dominate on all tested instances

Originalsprog	Engelsk
Titel	Proceedings of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence
Forlag	Association for Computing Machinery
Publikationsdato	2008
Sider	799-800
ISBN (Trykt)	978-1-58603-891-5
Status	Udgivet - 2008

Emneord

Binary Decision Diagrams
BDDs Compression
Linear Time Algorithms
Empirical Comparisons
Data Compression Techniques

Adgang til dokumentet

http://arxiv.org/abs/0805.3267

Citationsformater

@inproceedings{6f4226f0f6b611dd9b71000ea68e967b,

title = "Compressing Binary Decision Diagrams",

abstract = "The paper introduces a new technique for compressing Binary Decision Diagrams in those cases where random access is not required. Using this technique, compression and decompression can be done in linear time in the size of the BDD and compression will in many cases reduce the size of the BDD to 1-2 bits per node.Empirical results for our compression technique are presented, including comparisons with previously introduced techniques, showing that the new technique dominate on all tested instances",

keywords = "Binary Decision Diagrams, BDDs Compression, Linear Time Algorithms, Empirical Comparisons, Data Compression Techniques, Binary Decision Diagrams, BDDs Compression, Linear Time Algorithms, Empirical Comparisons, Data Compression Techniques",

author = "Hansen, {Esben Rune} and Satti, {Srinivasa Rao} and Peter Tiedemann",

year = "2008",

language = "English",

isbn = "978-1-58603-891-5 ",

pages = " 799--800 ",

booktitle = "Proceedings of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence",

publisher = "Association for Computing Machinery",

address = "United States",

}

Compressing Binary Decision Diagrams. / Hansen, Esben Rune; Satti, Srinivasa Rao; Tiedemann, Peter.
Proceedings of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence . Association for Computing Machinery, 2008. s. 799-800 .

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Compressing Binary Decision Diagrams

AU - Hansen, Esben Rune

AU - Satti, Srinivasa Rao

AU - Tiedemann, Peter

PY - 2008

Y1 - 2008

N2 - The paper introduces a new technique for compressing Binary Decision Diagrams in those cases where random access is not required. Using this technique, compression and decompression can be done in linear time in the size of the BDD and compression will in many cases reduce the size of the BDD to 1-2 bits per node.Empirical results for our compression technique are presented, including comparisons with previously introduced techniques, showing that the new technique dominate on all tested instances

AB - The paper introduces a new technique for compressing Binary Decision Diagrams in those cases where random access is not required. Using this technique, compression and decompression can be done in linear time in the size of the BDD and compression will in many cases reduce the size of the BDD to 1-2 bits per node.Empirical results for our compression technique are presented, including comparisons with previously introduced techniques, showing that the new technique dominate on all tested instances

KW - Binary Decision Diagrams

KW - BDDs Compression

KW - Linear Time Algorithms

KW - Empirical Comparisons

KW - Data Compression Techniques

KW - Binary Decision Diagrams

KW - BDDs Compression

KW - Linear Time Algorithms

KW - Empirical Comparisons

KW - Data Compression Techniques

M3 - Article in proceedings

SN - 978-1-58603-891-5

SP - 799

EP - 800

BT - Proceedings of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence

PB - Association for Computing Machinery

ER -