Proceedings

A Simplifier for Propositional Formulas with Many Binary Clauses

Download BibTeX Cite

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 515-521.

© 2001 International Joint Conferences on Artificial Intelligence

Abstract

Deciding whether a propositional formula in conjunctive normal form is satisfiable (SAT) is an NPcomplete problem. The problem becomes linear when the formula contains binary clauses only. Interestingly, the reduction to SAT of a number of well-known and important problems – such as classical AI planning and automatic test pattern generation for circuits – yields formulas containing many binary clauses. In this paper we introduce and experiment with 2- SIMPLIFY , a formula simplifier targeted at such problems. 2- SIMPLIFY constructs the implication graph corresponding to the binary clauses in the formula and uses this graph to deduce new unit literals. The deduced literals are used to simplify the formula and update the graph, and so on, until stabilization. Finally, we use the graph to construct an equivalent, simpler set of binary clauses. Experimental evaluation of this simplifier on a number of bench-mark formulas produced by encoding AI planning problems prove 2- SIMPLIFY to be fast and effective.

  1. [Aspvall et al., 1979] B. Aspvall, M. Plass, and R. Tarjan. A linear-time algorithm for testing the truth of certain quan- tified boolean formulas. Information Processing Letters, 8:121-123, 1979.
  2. [Bayardo and Schrag, 1997] R. J. Bayardo and R. C. Schrag. Using CSP look-back techniques to solve real-world SAT instances. In Proc. AAAI-97, pages 203-208, 1997.
  3. [Brafman, 1999] R. I. Brafman. Reachability, relevance, res- olution, and the planning as satisfiability approach. In IJ- CAI'99, pages 976-981, 1999. IJCAI
  4. Cook, 1971
  5. S. A. Cook. The complexity of theorem prov- ing procedures. In Proceedings of the Third ACM Sympo- sium on Theory of Computing. ACM, 1971.
  6. [Davis et al., 1962] M. Davis, G. Logemann, and D. Love- land. A machine program for theorem proving. Commu- nication of the ACM, 5(7):394-397, July 1962.
  7. [Ernst et al., 1997] M. D. Ernst, T. D. Millstein, and D. S. Weld. Automatic SAT-compilation of planning problems. In Proceedings of the International Joint Conference on Artificial Intelligence, 1997. IJCAI
  8. [Gomes et al., 1998] C. P. Gomes, B. Selman, and H. Kautz. Boosting combinatorial search through randomization. In Proc. of 15th Nat. Conf. AI, pages 431-437, 1998.
  9. [Kautz and Selman, 1996] H. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proc. of the 13th National Conference on AI (AAAI'96), pages 1194-1201, 1996.
  10. [Kautz and Selman, 1999] H. Kautz and B. Selman. Unify- ing sat-based and graph-based planning. In Proc. 16th Intl. Joint Conf. on AI (IJCAI'99), pages 318-325, 1999. IJCAI
  11. [Larrabee, 1992] T. Larrabee. Test pattern generation using boolean satisfiability. IEEE Transactions on Computer- Aided Design, pages 4-15, January 1992.
  12. [Li and Anbulagan, 1997] C. M. Li and Anbulagan. Heuris- tics based on unit propagation for satisfiability problems. In Proc. IJCAI-97, 1997. IJCAI
  13. [Robinson, 1965] J. A. Robinson. Automatic deduction with hyper-resolution. Int. J. of Com. Math, 1:227-234, 1965.
  14. [Selman et al., 1992] B. Selman, H. J. Levesque, and D. Mitchell. Gsat: A new method for solving hard sat- isfiability problems. In Proc. of the 10th National Conf. on AI (AAAI '92), pages 440-446, 1992.
  15. [Selman et al., 1994] Bart Selman, Henry A. Kautz, and B. Cohen. Noise strategies for improving local search. In Proc. Nat. Conf. on AI, pages 337-343, 1994.
  16. [Shtrichman, 2000] O. Shtrichman. Tuning sat checkers for bounded model checking. In E.A. Emerson and A.P. Sistla, editors, Computer Aided Verification 2000, 2000.
  17. [Van Gelder and Tsuji, 1996] A. Van Gelder and Y. K. Tsuji. Satisfiability testing with more reasoning and less guess- ing. In D. S. Johnson and M. Trick, editors, Cliques, Col- oring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, 1996.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards