×

zbMATH — the first resource for mathematics

Boolean Gröbner bases. Theory, algorithms and applications. (English) Zbl 1205.13001
Berlin: Logos Verlag; Kaiserslautern: TU Kaiserslautern, Fachbereich Mathematik (Diss. 2010) (ISBN 978-3-8325-2597-2/pbk). x, 149 p. (2010).
This is the publication of the PhD thesis of the author. The central part contains the theory, algorithms and applications of Boolean Gröbner bases, i.e. Gröbner bases of ideals resp. modules in Boolean rings (special quotient rings of polynomial rings: \(B=\mathbb{F}_2[x_1, \ldots, x_n]/\langle x_1^2-x_1, \ldots, x_n^2-x_n\rangle\)). Using the classical algorithms one can compute Gröbnerbases in \(B\) just considering the given ideal in \(\mathbb{F}_2[x_1, \ldots, x_n]\) and adding the polynomials \(x^2_1-x_1, \ldots, x_n^2-x_n\). This is not efficient if the number of variables is large. The new idea of the author is to present the polynomials as so–called 2DD’s (zero–suppressed decision diagrams) instead of a list of monomials. The new data structures and the corresponding basic operations together with several algebraic algorithms lead to a high performance implementation to compute Gröbner bases in Boolean rings: PolyBoRi. PolyBoRi will be a part of Singular. Applications to problems of formal verification resp. cryptoanalysis have been spectacular.

MSC:
13-02 Research exposition (monographs, survey articles) pertaining to commutative algebra
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
PDF BibTeX Cite