Internal representation of Boolean polynomials in the form of ZDD diagrams
Yu.A.Blinkov, P.V.Fokin
(Department of Mathematics and Mechanics, Saratov State University, Saratov)
E-mail address: BlinkovUA@info.sgu.ru, fokinpv@gmail.com
In the given talk we apply ZDD (Zero-suppressed Decision Diagrams) as data structures for internal representation of multivariate polynomials in a Boolean ring. For some classes of Boolean polynomials the space complexity of this representation will be estimated. Experimental analysis of computational efficiency of manipulation with ZDD in construction of involutive bases will also be done.
[1] Shin ichi Minato. Zero-suppressed bdds for set manipulation in combinatorial problems. In Proceedings of the 30th international Design Automation Conference, DAC ’93, pages 272–277, New York, NY, USA, 1993. ACM.
[2] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional, 12th edition, March 2009.
[3] Michael Brickenstein and Alexander Dreyer. Polybori: A framework for gršobner-basis computations with boolean polynomials. Journal of Symbolic Computation, 44(9):1326–1345, 2009. Effective Methods in Algebraic Geometry.
[4] Michael Brickenstein, Alexander Dreyer, Gert-Martin Greuel, Markus Wedler, and Oliver Wienand. New developments in the theory of gršobner bases and applications to formal verification. Journal of Pure and Applied Algebra, 213(8):1612–1635, 2009. Theoretical Effectivity and Practical Effectivity of Gršobner Bases.
[5] F. Somenzi. Cudd: Cu decision diagram package release, 1998.
[6] V. P. Gerdt, M. V. Zinin, and Yu. A. Blinkov. On computation of boolean involutive bases. Program. Comput. Softw., 36:117–123, March 2010.
Внутреннее представление булевских многочленов в виде ZDD-диаграмм
Ю.А. Блинков, П.В. Фокин
(Саратовский Государственный Университет)
E-mail address: BlinkovUA@info.sgu.ru, fokinpv@gmail.com
В докладе будет рассмотрено применение ZDD-диаграмм (Zero-suppressed Decision Diagram) в качестве внутреннего представления многочленов в булевом кольце. Для некоторых классов булевских многочленов и для указанного представления будет дана оценка сложности по требуемой памяти. Выполнена экспериментальная проверка эффективности работы с ZDD-диаграммами при построении инволютивных базисов средствами языков C/C++.
[1] Shin ichi Minato. Zero-suppressed bdds for set manipulation in combinatorial problems. In Proceedings of the 30th international Design Automation Conference, DAC ’93, pages 272–277, New York, NY, USA, 1993. ACM.
[2] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional, 12th edition, March 2009.
[3] Michael Brickenstein and Alexander Dreyer. Polybori: A framework for gršobner-basis computations with boolean polynomials. Journal of Symbolic Computation, 44(9):1326–1345, 2009. Effective Methods in Algebraic Geometry.
[4] Michael Brickenstein, Alexander Dreyer, Gert-Martin Greuel, Markus Wedler, and Oliver Wienand. New developments in the theory of gršobner bases and applications to formal verification. Journal of Pure and Applied Algebra, 213(8):1612–1635, 2009. Theoretical Effectivity and Practical Effectivity of Gršobner Bases.
[5] F. Somenzi. Cudd: Cu decision diagram package release, 1998.
[6] V. P. Gerdt, M. V. Zinin, and Yu. A. Blinkov. On computation of boolean involutive bases. Program. Comput. Softw., 36:117–123, March 2010.