Zhegalkin Polynomial SAT Solver : Zhegalkin SAT Solver (ZPSAT) is a efficient alternative to solve Boolean functions systems

ISBN-13: 9786202165372 / Angielski / Miękka / 2019 / 52 str.

Jorge Fernandez Davila

Opis

Polynomial systems are fundamental tools in the solution of hard problems in science and engineering such as robotics, automated reasoning, artificial intelligence and signal processing. Similarly, from the early days of the digital era, Boolean variables have been the foundations of the computer operations. Hence, the application of common algebraic techniques to Boolean algebra is used now as a method to solve complex Boolean equation systems that before were only intended to solve using Boolean logic techniques. The aim of this project is to demonstrate that Zhegalkin polynomials (also known as Algebraic Normal Form - ANF) are an alternative way to represent Boolean functions. In order to test the hypothesis, a Zhegalkin SAT Solver (ZPSAT) was developed. The results conducted after the testing concluded that ZPSAT can solve a conjunction of XOR equations efficiently in terms of reliability and computing time. The heuristic used to build ZPSAT was based mainly on the concepts used by the Horn Formulae and a Fast-Multiplication method of two ANF polynomials known as Mobius transform.

O autorze

Fernandez Davila, Jorge
Ingeniero de Sistemas con énfasis en los proyectos de desarrollo de Software. Maestría en Ciencias Avanzadas de la Computación en la Universidad de Kent, con mención en Inteligencia Artificial. Sus áreas de interés son: Redes Neuronales Cognitivas, Computación Bio-Inspirada, Descubrimiento de Conocimiento, Computación Paralela y Distribuida.