<?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-22T14:32:33Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/9587" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/9587</identifier><datestamp>2017-03-21T14:21:41Z</datestamp><setSpec>com_10012_9900</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9908</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="7df91ab2-63ef-4abb-a198-896df4e54be4" confidence="600">Juma, Nahid</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2015-08-26T14:27:14Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2015-08-26T14:27:14Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2015-08-26</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/9587</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This work studies the computational complexity of a tunable static type inference problem which was introduced in prior research [1]. The problem was assumed to be inherently difficult, without evidence, and a SAT solver was used to obtain a solution. In this thesis, we analyze the complexity of the inference problem. We prove that it is indeed highly unlikely that the problem can be solved efficiently. We also prove that the problem cannot be approximated efficiently to within a certain factor. We discuss the computational complexity of three restricted but useful versions of the problem, showing that whilst one of them can be solved in polynomial time, the other two are still inherently difficult. We discuss our efforts and the roadblocks we faced while attempting to conduct experiments to gain further insight into the properties which distinguish between hard and easy instances of the problem.&#xd;
&#xd;
References:&#xd;
[1]  W. Dietl, M. D. Ernst and P. Müller, Tunable Static Inference for Generic Universe Types, European Conference on Object-Oriented Programming (ECOOP), July 2011, Best Paper Award.</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">Type Inference</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computational Complexity</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Generic Universe Types</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Complexity Analysis of Tunable Type Inference for Generic Universe Types</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">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Applied Science</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>