IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Minimization, Learning, and Conformance Testing of Boolean Programs

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/11210

Files in this item

File Description Format
PDF Minimization, L ... ng of Boolean Programs.pdf (330KB) (no description provided) PDF
Title: Minimization, Learning, and Conformance Testing of Boolean Programs
Author(s): Kumar, Viraj; Madhusudan, P.; Viswanathan, Mahesh
Subject(s): Boolean programs minimization learning conformance testing
Abstract: Boolean programs with recursion are convenient abstractions of sequential, imperative programs. Recursive state machines (RSM) serve as machine models for Boolean programs and are semantically equivalent to pushdown automata. While pushdown automata cannot be minimized, motivated by the special structure of RSMs, we define a notion of modular VPA and show that for the class of languages accepted by such automata, unique minimal modular VPA exist. Using this we obtain \emph{approximate} minimization theorems for RSMs, where we show we can construct RSMs that are at most $k$ times the minimal RSM, where $k$ is the maximum number of parameters in a module. Our characterization of the minimum RSM leads to an active learning algorithm (with a minimally adequate teacher) for context free languages in terms of modular VPAs. We also present an algorithm that constructs complete test suites for Boolean program specifications. Finally, we apply our results for learning and test generation to perform model checking of black-box Boolean programs.
Issue Date: 2006-06
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11210
Other Identifier(s): UIUCDCS-R-2006-2736
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-21
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 225
  • Downloads this Month: 6
  • Downloads Today: 1

Browse

My Account

Information

Access Key