Fast incremental unit propagation by unifying watched-literals and local repair

The propositional satisfiability problem has been studied extensively due to its theoretical significance and applicability to a variety of fields including diagnosis, autonomous control, circuit testing, and software verification. In these applications, satisfiability problem solvers are often used to solve a large number of problems that are essentially the same and only differ from each other by incremental alterations. Furthermore, unit propagation is a common component of satisfiability problem solvers that accounts for a considerable amount of the solvers' computation time. Given this knowledge, it is desirable to develop incremental unit propagation algorithms that can efficiently perform changes between similar theories. This thesis introduces two new incremental unit propagation algorithms, called Logic-based Truth Maintenance System with Watched-literals and Incremental Truth Maintenance System with Watched-literals. These algorithms combine the strengths of the Logic-based and Incremental Truth Maintenance Systems designed for generic problem solvers with a state-of-the-art satisfiability solver data structure called watched literals.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2006

Author dc:creator

• Qu, Shen, S.M. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Brian C. Williams.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/37691

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/37691