Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

A simplifier for propositional formulas with many binary clauses.

Ronen I Brafman1

  • 1Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel. brafman@cs.bgu.ac.il

IEEE Transactions on Systems, Man, and Cybernetics. Part B, Cybernetics : a Publication of the IEEE Systems, Man, and Cybernetics Society
|September 17, 2004
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Prioritizing point-based POMDP solvers.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Societyยท2008
See all related articles

This study introduces 2-SIMPLIFY, a tool that simplifies Boolean satisfiability (SAT) problems with many binary clauses. It efficiently reduces problem complexity for AI planning and circuit testing.

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Computational Complexity

Background:

  • Boolean satisfiability (SAT) is NP-complete, but linear for binary clauses.
  • AI planning and circuit testing often generate SAT problems with numerous binary clauses.

Purpose of the Study:

  • Introduce and evaluate 2-SIMPLIFY, a novel formula simplifier.
  • Target simplification for SAT problems dominated by binary clauses.

Main Methods:

  • Constructing the transitive closure of the implication graph from binary clauses.
  • Deducing new unit literals to simplify the formula iteratively.
  • Stabilizing the simplification process and updating the graph.

Main Results:

Related Experiment Videos

  • 2-SIMPLIFY effectively simplifies formulas with many binary clauses.
  • The method constructs an equivalent, reduced set of binary clauses.
  • Experimental results demonstrate utility on AI planning benchmark formulas.

    • Conclusions:

    • 2-SIMPLIFY is a valuable tool for specific SAT problem instances.
    • The approach offers significant simplification for problems derived from AI planning.