Files in this item

FilesDescriptionFormat

application/pdf

Minimization, L ... ng of Boolean Programs.pdf (330Kb)
(no description provided)PDF

Description

 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
﻿