On computation of Boolean involutive bases

1. Sakai, K. and Sato, Y., Boolean Gröbner Bases, ICOT Tech. Memorandum 448, 1988. Sakai, K., Sato, Y., and Menju, S., Boolean Gröbner Bases (Revised), ICOT Tech. Report 613, 1991. http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-E.html.

2. Faugère, J.-C. and Joux, A., Algebraic Cryptanalysis of Hidden Field Equations (HFE) Using Gröbner Bases, Lecture Notes in Computer Science, Springer, 2003, vol. 2729, pp. 44–60.

   Article  Google Scholar 

3. Faugère, J.-C., Gianni, P., Lazard, D., and Mora, T., Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering, J. Symbol. Computations, 1993, vol. 16, no. 4, pp. 329–344.

   Article  MATH  Google Scholar 

4. von zur Ghaten, J. and Gerhard, J., Modern Computer Algebra, Cambridge: Cambridge Univ. Press, 2003, 2nd edition.

   Google Scholar 

5. Chistov, A.L., Two Times Exponential Lower Bound on the Degree of System of Generators for a Polynomial Prime Ideal, Algebra I Analiz, 2008, vol. 20, no. 6, pp. 186–213.

   Google Scholar 

6. Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-completeness, New York: Freeman, 1978. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow: Mir, 1982.

   Google Scholar 

7. Papadimitriou, C.H., Computational Complexity, Reading, Mass.: Addison-Wesley, 1994.

   MATH  Google Scholar 

8. 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 report RR-5049, 2003.

9. Condrat, C. and Kalla, P., A Gröbner Basis Approach to CNF-Formulae Preprocessing. Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science, Springer, 2007, vol. 4424, pp. 618–631.

   Article  Google Scholar 

10. Brickenstein, M., Dreyer, A., Greuel, G.-M., and Wienand, O., New Developments in the Theory of Gröbner Bases and Applications to Formal Verification. arXiv:math.AC/0801.1177.

11. Gerdt, V.P. and Zinin, M.V., Involutive Method for Computing Gröbner Bases over F ₂, Programmirovanie, 2008, no. 4, pp. 8–24 [Programming Comput. Software (Engl. Transl.), 2008, vol. 34, no. 4, pp. 112–123].

12. Gerdt, V.P. and Zinin, M.V., A Pommaret Division Algorithm for Computing Gröbner Bases in Boolean Rings, Proc. of ISSAC 2008 (Hagenberg, 2008), ACM, 2008, pp. 191–203.

13. Tran, Q.-N., A P-SPACE Algorithm for Gröbner Bases Computation in Boolean Rings, PWASET, 2008, vol. 35, pp. 495–501.

    Google Scholar 

14. Sato, Y., Nagai, A., and Inoue, S., On the Computation of Elimination Ideals of Boolean Polynomial Rings, Lecture Notes in Artificial Intelligence, Springer, 2008, vol. 5081, pp. 334–348.

    Google Scholar 

15. Gerdt, V.P. and Blinkov, Yu.A., Involutive Bases of Polynomial Ideals, Math. Comput. Simulation, 1998, vol. 45, pp. 519–542. arXiv:math.AC/9912027; Minimal Involutive Bases. Ibid. pp. 543–560. arXiv:math. AC/9912029.

    Article  MATH  MathSciNet  Google Scholar 

16. Gerdt, V.P., Involutive Algorithms for Computing Gröbner Bases, Computational Commutative and Non-Commutative Algebraic Geometry, Cojocaru, S., Pfister, G., and Ufnarovski, V., Eds., Amsterdam: IOS, 2005, pp. 199–225. arXiv:math.AC/0501111.

    Google Scholar 

17. Dawson, C.M., Haselgrove, H.L., Hines, A.P., Mortimer, D., Nielsen, M.A., and Osborne, T.J., Quantum Computing and Polynomial Equations over the Finite Field Z2. arXiv:quant-ph/0408129.

18. Seiler, W.M., A Combinatorial Approach to Involution and Delta-Regularity I: Involutive Bases in Polynomial Algebras of Solvable Type; II: Structure Analysis of Polynomial Modules with Pommaret Bases, Preprints of Universität Kassel, 2007.

19. Plesken, W. and Robertz, D., Janet’s Approach to Presentations and Resolutions for Polynomials and Linear Pdes, Arch. Math., 2005, vol. 84, pp. 22–37.

    Article  MATH  MathSciNet  Google Scholar 

20. 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.

    Google Scholar 

21. Gerdt, V.P., On the Relation between Pommaret and Janet Bases, Proc. of Conf. “Computer Algebra in Scientific Computing” (CASC 2000), (2000), Berlin: Springer, 2000, pp. 164–171. arXiv:math.AC/0004100.

    Google Scholar 

22. Apel, J., Theory of Involutive Division and an Application to Hilbert Function, J. Symb. Computations, 1998, vol. 25, pp. 683–704.

    Article  MATH  MathSciNet  Google Scholar 

23. Cox, D., Little, J., and O’shea, D., Ideals, Varieties, and Algorithms, New York: Springer, 2007, 3d edition.

    MATH  Google Scholar 

24. Gerdt, V.P., Blinkov, Yu.A., and Yanovich, D.A., Construction of Janet Bases: I. Monomial Bases and II. Polynomial Bases, Proc. of the Conf. “Computer Algebra in Scientific Computing” (CASC’01), (2001), Ganzha, V.G., Mayr, E.W., and Vorozhtsov, E.V., Eds., Berlin: Springer, 2001, pp. 249–263.

    Google Scholar 

25. Gerdt, V.P. and Blinkov, Yu.A., Specialized Computer Algebra System GINV, Programmirovanie, 2008, no. 2, pp. 67–80 [Programming Comput. Software (Engl. Transl.), 2008, vol. 34, no. 2, pp. 112–123].

26. http://www-sop.inria.fr/saga/POL; http://www.math. uic.edu/~jan/demo.html.

27. Kornyak, V.V., On Compatibility of Discrete Relations, Lecture Notes in Computer Science, Springer, 2005, vol. 3718, pp. 272–284, arXiv:math-ph/0504048.

    Article  MathSciNet  Google Scholar 

Download references