Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3290282.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Conformance Testing and Error Explanation for Software Models
Author(s):Kumar, Viraj
Doctoral Committee Chair(s):Viswanathan, Mahesh
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
Abstract:Error explanation addresses the question of how to correct faults. Many heuristics have been proposed, but there has been little effort to characterize the complexity of the problem. Because this is a vital part of any verification endeavor, we analyze the complexity of the most popular error explanation heuristics as a function of the program model. We establish the hardness of error explanation according to one heuristic via an interesting reduction from the well-known hard problem of determining the smallest deterministic finite automaton that is consistent with a given sample of positively and negatively labeled inputs. We also prove that error explanation based on the second heuristic is tractable for several models that capture program behavior.
Issue Date:2007
Type:Text
Language:English
Description:82 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007.
URI:http://hdl.handle.net/2142/81782
Other Identifier(s):(MiAaPQ)AAI3290282
Date Available in IDEALS:2015-09-25
Date Deposited:2007


This item appears in the following Collection(s)

Item Statistics