Dissertation/Thesis Abstract

Boolean Satisfiability, Graph Problems, and Zeons
by Strotheide, Amanda, M.S., Southern Illinois University at Edwardsville, 2018, 30; 10844331
Abstract (Summary)

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.

Indexing (document details)
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
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest