<?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-22T10:52:28Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9580" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9580</identifier><datestamp>2017-03-21T14:33:49Z</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="812dc851-32cd-443b-bde9-5115b1c77728" confidence="600">Kumar, Neeraj</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-08-25T18:31:27Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-08-25T18:31:27Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-08-25</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2015</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/9580</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This thesis deals with determining appropriate width parameters of control flow graphs so that certain computationally hard problems of practical interest become efficiently solvable. A well-known result of Thorup states that the treewidth of control flow graphs arising from structured (goto-free) programs is at most six. However, since a control flow graph is inherently directed, it is very likely that using a digraph width measure would give better algorithms for problems where directional properties of edges are important. One&#xd;
such problem, parity game, is closely related to the μ-calculus model checking problem in software verification and is known to be tractable on graphs of bounded DAG-width, Kelly-width or entanglement.&#xd;
&#xd;
Motivated by this, we show that the DAG-width of control flow graphs arising from structured programs is at most three and give a linear-time algorithm to compute the corresponding DAG decomposition. Using similar techniques, we show that Kelly-width of control flow graphs is also bounded by three. Additionally, we also show that control flow graphs can have unbounded entanglement. In light of these results, we revisit the complexity of the μ-calculus model checking problem on these special graph classes and show that we can obtain better running times for control flow graphs.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">treewidth</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">DAG-width</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">entanglement</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Kelly-width</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">control flow graphs</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">mu-calculus model checking</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">special graph classes</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Graph-theoretic Properties of Control Flow Graphs and Applications</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Computer Science (David R. Cheriton School of)</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</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>