nach oben

Theory of Computing Systems

Erschienen in:

01.10.2016

On the Minimization of (Complete) Ordered Binary Decision Diagrams

verfasst von: Beate Bollig

Erschienen in: Theory of Computing Systems | Ausgabe 3/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions. Some applications work with a restricted variant called complete OBDDs which is strongly related to nonuniform deterministic finite automata. One of its complexity measures is the width which has been investigated in several areas in computer science like machine learning, property testing, and the design and analysis of implicit graph algorithms. For a given function the size and the width of a (complete) OBDD is very sensitive to the choice of the variable ordering but the computation of an optimal variable ordering for the OBDD size is known to be NP-hard. Since optimal variable orderings with respect to the OBDD size are not necessarily optimal for the complete model or the OBDD width and hardly anything about the relation between optimal variable orderings with respect to the size and the width is known, this relationship is investigated. Here, using a new reduction idea it is shown that the size minimization problem for complete OBDDs and the width minimization problem are NP-hard.

Vorheriger Artikel Distinguishing Two Probability Ensembles with One Sample from each Ensemble

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Bollig, B.: On the size of (generalized) OBDDs for threshold functions. Inf. Process. Lett. 109(10), 499–503 (2009)MathSciNetCrossRefMATH

Bollig, B.: On the complexity of some ordering problems. In: Proc. of MFCS, LNCS 8635, pp. 118–129. Springer (2014)

Bollig, B.: On the width of ordered binary decision diagrams. In: Proc. of COCOA, LNCS 8881, pp. 444–458. Springer (2014)

Bollig, B., Range, N., Wegener, I.: Exact OBDD bounds for some fundamental functions. Theory Comput. Syst. 47(2), 593–609 (2010)MathSciNetCrossRefMATH

Bollig, B., Wegener, I.: Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Comput. 45(9), 993–1002 (1996)CrossRefMATH

Bollig, B., Wegener, I.: Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems. J. Comput. Syst. Sci. 61(3), 558–579 (2000)MathSciNetCrossRefMATH

Brody, J., Matulef, K., Wu, C.: Lower bounds for testing computability by small width OBDDs. In: TAMC, LNCS 6648, pp. 320–331. Springer (2011)

Bryant, R.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677–691 (1986)CrossRefMATH

Díaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002)CrossRef

10.

Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)

11.

Ergün, F., Kumar, R., Rubinfeld, R.: On learning bounded-width branching programs. In: COLT, pp. 361–368 (1995)

12.

Fortune, F., Hopcroft, J., Schmidt, E.: The complexity of equivalence and containment for free single variable program schemes. In: Proc. of ICALP, LNCS 62, pp. 227–240. Springer (1978)

13.

Gavril, F.: Some NP-complete problems on graphs. In: 11th Conference on Information Science and Systems, pp. 91–95 (1977)

14.

Goldreich, O.: On testing computability by small width OBDDs. In: APPROX-RANDOM, pp. 574–587 (2010)

15.

Newman, I.: Testing membership in languages that have small width branching programs. SIAM J. Comput. 31(5), 1557–1570 (2002)MathSciNetCrossRefMATH

16.

Ochi, H., Ishiura, N., Yajima, S.: Breadth-first manipulation of SBDD of boolean functions for vector processing. In: DAC, pp. 413–416 (1991)

17.

Ochi, H., Yasuoka, K., Yajima, S.: Breadth-first manipulation of very large binary-decision diagrams. In: ICCAD, pp. 48–55 (1993)

18.

Ron, D., Tsur, G.: Testing computability by width-two OBDDs. Theor. Comput. Sci. 420, 64–79 (2012)MathSciNetCrossRefMATH

19.

Sawitzki, D.: The complexity of problems on implicitly represented inputs. In: Proc. of SOFSEM, LNCS 3831, pp. 471–482. Springer (2006)

20.

Sieling, D.: The nonapproximability of OBDD minimization. Inf. Comput. 172(2), 103–138 (2002)MathSciNetCrossRefMATH

21.

Sieling, D., Wegener, I.: NC-algorithms for operations on binary decision diagrams. Parallel Process. Lett. 3, 3–12 (1993)MathSciNetCrossRef

22.

Tani, S., Hamagushi, K., Yajima, S.: The complexity of the optimal variable ordering problems of a shared binary decision diagram. In: Proc. of ISAAC, LNCS 762, pp. 389–396. Springer (1993)

23.

Wegener, I.: The size of reduced OBDDs and optimal read-once branching programs for almost all boolean functions. IEEE Trans. Comput. 43(11), 1262–1269 (1994)MathSciNetCrossRefMATH

24.

Wegener, I.: Branching programs and binary decision diagrams: theory and applications. SIAM (2000)

25.

Woelfel, P.: Symbolic topological sorting with OBDDs. J. Discret. Algoritm. 4(1), 51–71 (2006)MathSciNetCrossRefMATH

Titel: On the Minimization of (Complete) Ordered Binary Decision Diagrams
verfasst von: Beate Bollig
Publikationsdatum: 01.10.2016
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 3/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-015-9657-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2016

Learning Sets of Antecedent-restricted Functional and Multivalued Dependencies with Queries

Counting the Number of Perfect Matchings in K 5-Free Graphs

Distinguishing Two Probability Ensembles with One Sample from each Ensemble

On the Advice Complexity of the k-server Problem Under Sparse Metrics

Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness

Network Formation for Asymmetric Players and Bilateral Contracting

Premium Partner