With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
Dissertation/Thesis Abstract
-
Other Available Formats:
-
Full Text - PDF
(426.76 KB)
It has been previously shown that given a finite set of clauses a corresponding graph can be constructed to help determine if a SAT problem in CNF is satisfiable by looking for cliques in the associated graph. This paper uses a similar method to convert the SAT problem to a finite graph. Differing from the traditional approach, in this case, the vertex incidence representation on a given Clifford algebra can be utilized on complement graphs to find independent sets. This approach gives a concrete method to determine not only if a SAT problem is satisfiable, but also yields all satisfying truth assignments.
| Advisor: | Staples, G. S. |
| Commitee: | Loreaux, Jireh, Parish, James |
| School: | Southern Illinois University at Edwardsville |
| Department: | Math |
| School Location: | United States -- Illinois |
| Source: | MAI 58/03M(E), Masters Abstracts International |
| Source Type: | DISSERTATION |
| Subjects: | Mathematics |
| Keywords: | Boolean satisfiability, Graph theory, Zeons |
| Publication Number: | 10844331 |
| ISBN: | 978-0-438-76908-3 |
