Files in this item



application/pdfMinimization, 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
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
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)

Item Statistics