A modular reduction of regular logic to classical logic

R Béjar, R Hahnle, F Manya - Proceedings 31st IEEE …, 2001 - ieeexplore.ieee.org
R Béjar, R Hahnle, F Manya
Proceedings 31st IEEE International Symposium on Multiple-Valued Logic, 2001ieeexplore.ieee.org
In this paper we first define a reduction/spl delta/that transforms an instance/spl Gamma/of
Regular-SAT into a satisfiability equivalent instance/spl Gamma//sup/spl delta//of SAT. The
reduction/spl delta/has interesting properties:(i) the size of/spl Gamma//sup/spl delta//is
linear in the size of/spl Gamma/,(ii)/spl delta/transforms regular Horn formulas into Horn
formulas, and (iii)/spl delta/transforms regular 2-CNF formulas into 2-CNF formulas. Second,
we describe a new satisfiability algorithm that determines the satisfiability of a regular 2-CNF …
In this paper we first define a reduction /spl delta/ that transforms an instance /spl Gamma/ of Regular-SAT into a satisfiability equivalent instance /spl Gamma//sup /spl delta// of SAT. The reduction /spl delta/ has interesting properties: (i) the size of /spl Gamma//sup /spl delta// is linear in the size of /spl Gamma/, (ii) /spl delta/ transforms regular Horn formulas into Horn formulas, and (iii) /spl delta/ transforms regular 2-CNF formulas into 2-CNF formulas. Second, we describe a new satisfiability algorithm that determines the satisfiability of a regular 2-CNF formula /spl Gamma/ in time O(|/spl Gamma/|log|/spl Gamma/|); this algorithm is inspired by the reduction /spl delta/. Third, we introduce the concept of renamable-Horn regular CNF formula and define another reduction /spl delta/' that transforms a renamable-Horn instance /spl Gamma/ of Regular-SAT into a renamable-Horn instance /spl Gamma//sup /spl delta/'/ of SAT. We use this reduction to show that both membership and satisfiability of renamable-Horn regular CNF formulas can be decided in time O(|/spl Gamma/|log|/spl Gamma/|).
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果