<?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-22T08:50:13Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/4485" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/4485</identifier><datestamp>2017-03-21T17:30:19Z</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="406b79a2-5186-4523-b682-cd27768c2658" confidence="600">Ben-David, Shoham</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2009-06-19T19:12:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2009-06-19T19:12:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2009-06-19T19:12:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2009</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/4485</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Model checking  is an automated technique for the verification of finite-state systems that is widely used in practice.&#xd;
In model checking, a model M is verified against a specification $\varphi$, exhaustively checking that the tree of all computations of M satisfies $\varphi$.&#xd;
When $\varphi$ fails to hold in M, the negative result is accompanied&#xd;
by a counterexample:  a computation in M that demonstrates the failure.&#xd;
State of the art model checkers apply Binary Decision Diagrams(BDDs) as well as satisfiability solvers for this task. However, both methods suffer from the state explosion problem, which restricts the application of model checking to only modestly sized systems. The importance of model checking makes it worthwhile to explore&#xd;
alternative technologies, in the hope &#xd;
of broadening the applicability&#xd;
of the technique to a wider class of systems.&#xd;
&#xd;
Description Logic (DL) is a family of knowledge representation formalisms  based on decidable fragments of first order logic.&#xd;
DL is used mainly for designing ontologies in information systems. In recent years several DL reasoners have been developed, demonstrating  an impressive capability to cope with very large ontologies.&#xd;
&#xd;
This work consists of two parts.  In the first we harness the growing ability of DL reasoners to solve model checking problems.&#xd;
We show how DL can serve as a natural setting for representing and solving a model checking problem, and present a variety of&#xd;
encodings that translate such problems into consistency queries in DL.&#xd;
Experimental results, using the Description Logic reasoner FaCT++, demonstrate that for some systems and properties, our method can&#xd;
outperform existing ones.&#xd;
&#xd;
In the second part we approach a different aspect of model checking. When a specification fails to hold in a model and a counterexample is presented to the user, the counterexample may itself be complex and difficult to understand. We propose an automatic technique  to find the computation steps and their associated variable values, that are of particular importance in generating the counterexample. We use the notion of causality to formally define a set&#xd;
of causes for the failure of the specification on the given counterexample. We give a linear-time algorithm to detect&#xd;
the causes, and we demonstrate how these causes can be presented to the user as a visual explanation of the failure.</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">Model Checking</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Description Logic</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Causality</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Applications of Description Logic and Causality in Model Checking</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>