Gröbner Bases for Boolean Function Minimization
International audience Boolean function minimization techniques try to find, for a given formula, a smaller equivalent formula. In this work, we present a novel technique for heuristic boolean function minimization. By using an algebraic encoding, we embed the minimization problem into an algebraic...
Main Authors: | , |
---|---|
Other Authors: | , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
1481
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-04315477 https://inria.hal.science/hal-04315477/document https://inria.hal.science/hal-04315477/file/short4.pdf |
Summary: | International audience Boolean function minimization techniques try to find, for a given formula, a smaller equivalent formula. In this work, we present a novel technique for heuristic boolean function minimization. By using an algebraic encoding, we embed the minimization problem into an algebraic domain, where algorithms for computing Gröbner bases are applicable. A Gröbner basis usually forms a compact representation of our encoded function. From the Gröbner basis, we then reconstruct an equivalent, more compact boolean formula. Our approach is the first to use Gröbner bases for function minimization. Combined with advances of algebraic Gröbner bases in satisfiability checking, this motivates further research on applications of Gröbner bases in the context of boolean logic. |
---|