Files in this item



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


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
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
Description:82 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007.
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