BIBasis, a package for REDUCE and Macaulay2 computer algebra systems to compute Boolean involutive and Gröbner bases. (English. Russian original) Zbl 1251.68309

Program. Comput. Softw. 38, No. 2, 92-101 (2012); translation from Programmirovanie 38, No. 2 (2012).
Summary: In this paper, we describe the BIBasis package designed for REDUCE and Macaulay2 computer algebra systems, which allows one to compute Boolean involutive bases and Gröbner bases. The implementations and user interfaces of the package for both systems are described in the respective sections of the paper. Also, we present results of comparisons of BIBasis with other packages and algorithms for constructing Boolean Gröbner bases available in the computer algebra systems.


68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
06E20 Ring-theoretic properties of Boolean algebras
68-04 Software, source code, etc. for problems pertaining to computer science
Full Text: DOI


[1] Gerdt, V.P. and Blinkov, Yu.A., Involutive Bases of Polynomial Ideals, Math. Comput. in Simulation, 1998, vol. 45, pp. 519–542; Minimal Involutive Bases, pp. 543–560. · Zbl 1017.13500
[2] Seiler, W.M., Involution: The Formal Theory of Differential Equations and its Applications in Computer Algebra. Algorithms and Computation in Mathematics, vol. 24, Springer, 2010. arXiv:math.AC/0501111 · Zbl 1205.35003
[3] Gerdt, V.P., Involutive Algorithms for Computing Gröbner Bases, in Computational Commutative and Non-Commutative Algebraic Geometry, Amsterdam: IOS, 2005, pp. 199–225. · Zbl 1104.13012
[4] Faugère, J.-C. and Joux, A., Algebraic Cryptanalysis of Hidden Field Equations (HFE) Using Gröbner Bases, Lecture Notes in Computer Science, vol. 2729, Springer, 2003, pp. 44–60. · Zbl 1122.94371
[5] Brickenstein, M., Dreyer, A., Greuel, G.-M., and Wienand, O., New Developments in the Theory of Gröbner Bases and Applications to Formal Verification, J. Pure Appl. Algebra, 2009, vol. 213, pp. 1612–1635. arXiv:math.AC/0801.1177 · Zbl 1164.68019
[6] Gerdt, V.P. and Zinin, M.V., A Pommaret Division Algorithm for Computing Gröbner Bases in Boolean Rings, Proc. of the ISSAC 2008, ACM, 2008, pp. 95–102.
[7] Gerdt, V.P. and Zinin, M.V., Involutive Method for Computing Gröbner Bases over F 2, Programming Comput. Software, 2008, vol. 34, no. 4, pp. 191–203. · Zbl 1185.68868
[8] Gerdt, V.P., Zinin, M.V., and Blinkov, Yu.A., On Computation of Boolean Involutive Bases, Programming Comput. Software, 2010, vol. 36, no. 2, pp. 117–128. · Zbl 1214.68472
[9] Hearn, A.., REDUCE, a Portable General-Purpose Computer Algebra System. http://www.reduce-algebra.com/ . 2009.
[10] Grayson, D.R. and Stillman, M.E., Macaulay2, a Software System for Research in Algebraic Geometry. http://www.math.uiuc.edu/Macaulay2 . 2011.
[11] Bardet, M., Faugère, J.-C., and Salvy, B., Complexity of Gröbner Basis Computation for Semi-Regular Overdetermined Sequences over \(\mathbb{F}_2 \) with Solutions in \(\mathbb{F}_2 \) , INRIA Rep. RR-5049, 2003.
[12] Becker, T., Weispfenning, V., and Kredel, H., Gröbner Bases. A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics, vol. 141, New York: Springer, 1993. · Zbl 0772.13010
[13] Neun, W., Portable Standard Lisp. http://www2.zib.de/Symbolik/reduce/ . 1999.
[14] Codemist Standard LISP. http://www.codemist.co.uk . 2002.
[15] https://reduce-algebra.svn.sourceforge.net/svnroot/reduce-algebra/trunk
[16] Eisenbud, D., Grayson, D.R., Stillman, M.E., and Sturmfels B., Computations in Algebraic Geometry with Macaulay2, in Algorithms and Computations in Mathematics, vol. 8, Berlin: Springer, 2002. http://www.math.uiuc.edu/Macaulay2/Book/ · Zbl 0973.00017
[17] svn://svn.macaulay2.com/Macaulay2/trunk/M2/
[18] Bini, D. and Mourrain, B., Polynomial Test Suite, 2006. http://www-sop.inria.fr/saga/POL . 2006; Verschelde, J., The Database of Polynomial Systems. http://www.math.uic.edu/ jan/demo.html . 2011.
[19] Kornyak, V.V., On Compatibility of Discrete Relations, Lecture Notes in Computer Science, vol. 3718, Springer, 2005, pp. 272–284. http://arxiv.org/abs/math-ph/0504048 · Zbl 1169.68663
[20] Hoos, H.H. and Stutzle, T., SATLIB: An Online Resource for Research on SAT, in SAT 2000, Gent, I.P., Maaren, H.v., and Walsh, T., Eds., IOS Press, 2000, pp. 283–292. http://www.satlib.org · Zbl 0979.68128
[21] Hinkelmann, F. and Arnold, E., Fast Gröbner Basis Computation for Boolean Polynomials. http://arxiv.org/abs/1010.2669v1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.