2026-09-19T07:47:52Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/81782 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Viswanathan, Mahesh Kumar, Viraj 2015-09-25T20:20:26Z 2015-09-25T20:20:26Z 10000-01-01 2007 2007 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. http://hdl.handle.net/2142/81782 (MiAaPQ)AAI3290282 eng Computer Science Conformance Testing and Error Explanation for Software Models text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.