<?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-22T19:13:33Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/5619" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/5619</identifier><datestamp>2017-03-21T17:42:08Z</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="d9f9a180-0e6c-4043-be3a-f2a61cb6cbfa" confidence="600">Langari, Zarrin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2010-11-01T15:12:09Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2010-11-01T15:12:09Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2010-11-01T15:12:09Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2010-10-29</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/5619</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Communication protocols, a class of critical systems, play an important role in industry. These protocols are critical because the tolerance for faults in these systems is low and it is highly desirable that these systems work correctly. Therefore, an effective methodology for describing and verifying that these systems behave according to their specifications is vitally important.&#xd;
Model checking is a verification technique in which a mathematically precise model of the system, either concrete or with abstraction, is built and a specification of how the system should  behave is given. Then the system is considered correct if its model satisfies its specification. However, due to their size and complexity, critical systems, such as communication systems, are notoriously resistant to formal modelling and verification.&#xd;
&#xd;
&#xd;
In this thesis, we propose using graph transformation systems (GTSs), a visual&#xd;
semantic modelling approach, to model the behaviour of dynamically evolving  communication protocols. Then, we show  how a GTS model can facilitate verification of invariant properties of potentially unbounded communication systems. Finally, due to the use of similar isomorphic components in communication systems, we show how  to exploit symmetries of these dynamically evolving models described by GTSs, to reduce the size of the model under verification.&#xd;
&#xd;
&#xd;
We use graph transformation systems to provide an expressive and intuitive visual description of the system state as a graph and for the computations of the system as a finite set of rules that transform the state graphs. Our model is well-suited for describing the behaviour of individual components, error-free communication channels amongst the components, and dynamic component creation and elimination.  Thus, the structure of the generated model closely resembles the way in which communication protocols are typically separated into three levels: the first describing local features or components, the second characterizing interactions among components, and the third showing the evolution of the component set.  The graph transformation semantics  follows this scheme, enabling a clean separation of concerns when describing a protocol. This separation of concerns is a necessity for formal analysis of system behaviour.&#xd;
&#xd;
&#xd;
We prove that the finite set of graph transformation rules that describe behaviour of the system can be used to perform  verification for invariant properties of the system. We show that if a property is preserved by the finite set of transformation rules describing the system model, and if the initial state satisfies the property, then the property is an invariant of the system model. Therefore, our verification method may avoid the  explicit analysis of the  potentially enormous state space that the transformation rules encode.&#xd;
&#xd;
In this thesis, we also develop symmetry reduction techniques applicable to dynamically evolving GTS models. The necessity to extend the existing symmetry reduction techniques arises because these techniques  are not applicable to dynamic models such as those described by GTSs, and, in addition, these existing techniques  may offer only limited reduction to systems that are not fully symmetric.  We present an  algorithm for generating a symmetry-reduced quotient model directly from a set of graph transformation rules. The generated quotient model  is bisimilar to the model under verification and may be exponentially smaller than that model.</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">verification</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph transformation</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Modelling and Analysis using Graph Transformation Systems</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>