Minimization, Learning, and Conformance Testing of Boolean Programs

Kumar, Viraj; Madhusudan, P.; Viswanathan, Mahesh

Permalink

https://hdl.handle.net/2142/11210 Copy

Description

Title

Minimization, Learning, and Conformance Testing of Boolean Programs

Author(s)

• Kumar, Viraj
• Madhusudan, P.
• Viswanathan, Mahesh

Issue Date

2006-06

Keyword(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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11210

Copyright and License 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).

Owning Collections