Makowski, Ryszard - ed. ; Zarzycki, Jan - ed.
The paper concerns the problem of Boolean satisfiability checking, which is recognized as one of the most important issues in the field of modern digital electronic system verification and design. The paper analyzes different strategies and scenarios of the proving process, and presents a modified and extended version of the autor`s FUDASAT algorithm. ; The original FUDASAT methodology is an intuitive approach that employs a commonsense reasoning methodology. The main objective of the work is to investigate the SAT-solving process and try to formulate a set of rules controlling the reasoning process of the FUDASAT inference engine. In comparison with the autor`s previous works, the paper introduces new mechanisms: hypergraph analysis, multiple variable assignments and search space pruning algorithms. ; The approach considers only 3-SAT class functions, although a generalization of the method is discussed as well. The presented approach has been tested on various benchmarks and compared with the original pure FUDASAT algorithm as well as with other algorithms known from the literature. Finally, the benefits of the proposed SAT solving technique are summarized.
Zielona Góra: Uniwersytet Zielonogórski
AMCS, volume 24, number 2 (2014) ; kliknij tutaj, żeby przejść
Biblioteka Uniwersytetu Zielonogórskiego
2024-04-24
2024-04-24
15
https://zbc.uz.zgora.pl/repozytorium/publication/88745
Nazwa wydania | Data |
---|---|
Selection of search strategies for solving 3-SAT problems | 2024-04-24 |
Gosti, Wilsin Villa, Tiziano Saldanha, Alex Sangiovanni-Vincentelli, Alberto L. Korbicz, Józef - red.
Klimek, Radosław Korbicz, Józef - red. Uciński, Dariusz - red.