{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81782"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81782","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Conformance Testing and Error Explanation for Software Models","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kumar, Viraj"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Viswanathan, Mahesh"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:20:26Z","date_published":"2015-09-25T20:20:26Z","updated_at":"2026-07-22T22:26:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3290282"],"render_values":[{"text":"(MiAaPQ)AAI3290282","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81782","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Viswanathan, Mahesh"]},{"key":"dc:creator","label":"Author","values":["Kumar, Viraj"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:20:26Z","10000-01-01","2007"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81782","(MiAaPQ)AAI3290282"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2015-09-25T20:20:26Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3290282.pdf: 3051349 bytes, checksum: c8a5f7c3cac349d99cff91495a3a1f0e (MD5) Previous issue date: 2007","Embargo set by: Seth Robbins for item 83063 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","82 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007."]},{"key":"dc:title","label":"Title","values":["Conformance Testing and Error Explanation for Software Models"]}]}],"canonical_facts":{"dc:contributor":["Viswanathan, Mahesh"],"dc:creator":["Kumar, Viraj"],"dc:date":["2015-09-25T20:20:26Z","10000-01-01","2007"],"dc:description":["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.","Made available in DSpace on 2015-09-25T20:20:26Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3290282.pdf: 3051349 bytes, checksum: c8a5f7c3cac349d99cff91495a3a1f0e (MD5) Previous issue date: 2007","Embargo set by: Seth Robbins for item 83063 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","82 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2007."],"dc:identifier":["http://hdl.handle.net/2142/81782","(MiAaPQ)AAI3290282"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Conformance Testing and Error Explanation for Software Models"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:16Z"}