Introducing fuzzy default logic into WalkSAT algorithm

Author

Pulka, Andrzej ; Milik, Adam

Author_Institution

Dept. of Autom. Control, Electron. & Comput. Sci., Silesian Univ. of Technol., Gliwice, Poland

fYear

2014

fDate

11-13 Sept. 2014

Firstpage

1

Lastpage

4

Abstract

The paper presents an approach to Boolean satisfiability checking. The work is based on fuzzy default logic (FDL) introduced by one of the authors on HIS´09 conference. The starting point of the presented approach is WalkSAT algorithm. Authors discuss heuristic variable flipping techniques that employ commonsense reasoning methodology (FDL) and searching space pruning techniques implemented in the FUDASAT algorithm. The new algorithm called JumpSAT is presented on the examples. The paper shows interesting results of some experiments that shows effectiveness of the new proposed technique in comparison to the FUDASAT approach.

Keywords

Boolean functions; common-sense reasoning; computability; formal verification; fuzzy logic; search problems; Boolean satisfiability checking; FDL; FUDASAT algorithm; JumpSAT algorithm; WalkSAT algorithm; commonsense reasoning methodology; formal verification; fuzzy default logic; heuristic variable flipping techniques; searching space pruning techniques; Aerospace electronics; Algorithm design and analysis; Artificial intelligence; Benchmark testing; Cognition; Conferences; Search problems; Boolean satisfiability; CNF; Formal verification; Heuristic search; SAT solving;

fLanguage

English

Publisher

ieee

Conference_Titel

Signals and Electronic Systems (ICSES), 2014 International Conference on

Conference_Location

Poznan

Type

conf

DOI

10.1109/ICSES.2014.6948719

Filename

6948719