<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T12:14:34Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/5322" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/5322</identifier><datestamp>2017-03-21T14:49:38Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="b7555ba2-c0d9-40a4-a9cc-48ef484ab777" confidence="600">Li, Wei</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2010-08-03T18:47:27Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2010-08-03T18:47:27Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2010-08-03T18:47:27Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2010</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/5322</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Boolean propositional satisfiability (SAT) and probabilistic reasoning represent&#xd;
two core problems in AI. Backtracking based algorithms have been applied in both&#xd;
problems. In this thesis, I investigate structure-based techniques for solving real world&#xd;
SAT and Bayesian networks, such as software testing and medical diagnosis instances.&#xd;
When solving a SAT instance using backtracking search, a sequence of decisions&#xd;
must be made as to which variable to branch on or instantiate next. Real world problems&#xd;
are often amenable to a divide-and-conquer strategy where the original instance&#xd;
is decomposed into independent sub-problems. Existing decomposition techniques&#xd;
are based on pre-processing the static structure of the original problem. I propose&#xd;
a dynamic decomposition method based on hypergraph separators. Integrating this&#xd;
dynamic separator decomposition into the variable ordering of a modern SAT solver&#xd;
leads to speedups on large real world SAT problems.&#xd;
Encoding a Bayesian network into a CNF formula and then performing weighted&#xd;
model counting is an effective method for exact probabilistic inference. I present two&#xd;
encodings for improving this approach with noisy-OR and noisy-MAX relations. In&#xd;
our experiments, our new encodings are more space efficient and can speed up the&#xd;
previous best approaches over two orders of magnitude.&#xd;
The ability to solve similar problems incrementally is critical for many probabilistic&#xd;
reasoning problems. My aim is to exploit the similarity of these instances by&#xd;
forwarding structural knowledge learned during the analysis of one instance to the&#xd;
next instance in the sequence. I propose dynamic model counting and extend the dynamic&#xd;
decomposition and caching technique to multiple runs on a series of problems&#xd;
with similar structure. This allows us to perform Bayesian inference incrementally as&#xd;
the evidence, parameter, and structure of the network change. Experimental results&#xd;
show that my approach yields significant improvements over previous model counting&#xd;
approaches on multiple challenging Bayesian network instances.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">SAT</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Model Counting</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Bayesian networks</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Backtracking Algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Noisy-OR</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Noisy-MAX</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Exploiting Structure in Backtracking Algorithms for Propositional and Probabilistic Reasoning</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>