Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Gröbner-free normal forms for boolean polynomials

: Brickenstein, M.; Dreyer, A.


Gonzales-Vega, L. ; Association for Computing Machinery -ACM-, Special Interest Goup on Symbolic and Algebraic Manipulation -SIGSAM-:
ISSAC 2008, ACM-SIGSAM International Symposium on Symbolic and Algebraic Computation. Proceedings : July 20-23, 2008, Hagenberg, Austria
New York: ACM, 2008
ISBN: 978-1-59593-904-3
International Symposium on Symbolic and Algebraic Computation (ISSAC) <2008, Hagenberg>
Conference Paper
Fraunhofer ITWM ()

This paper introduces a new method for interpolation of Boolean functions using Boolean polynomials. It was motivated by some problems arising from computational biology, for reverse engineering the structure of mechanisms in gene regulatory networks. For this purpose polynomial expressions have to be generated, which match known state combinations observed during experiments. Earlier approaches using Gröbner techniques have not been powerful enough to treat real-world applications. The proposed method avoids expensive Gröbner basis computations completely by directly calculating reduced normal forms. The problem statement can be described by Boolean polynomials, i.e. polynomials with coefficients in {0,1} and a degree bound of one. Therefore, the reference implementations mentioned in this work are built on the top of the PolyBoRi framework, which has been designed exclusively for the treatment of this special class of polynomials. A series of randomly generated examples is used to demonstrate the performance of the direct method. It is also compared with other approaches, which incorporate Gröbner basis computations.