With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
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 |