Minimization, learning, and conformance testing of boolean programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Boolean programs with recursion are convenient abstractions of sequential imperative programs, and can be represented as recursive state machines (RSMs) or pushdown automata. Motivated by the special structure of RSMs, we define a notion of modular visibly pushdown automata (modular VPA) and show that for the class of languages accepted by such automata, unique minimal modular VPA exist. This yields an efficient approximate minimization theorem that minimizes RSMs to within a factor of k of the minimal RSM, where k is the maximum number of parameters in any module. Using the congruence defined for minimization, we show 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 on learning and test generation to perform model checking of black-box Boolean programs.

Original languageEnglish (US)
Title of host publicationCONCUR 2006 - Concurrency Theory - 17th International Conference, CONCUR 2006, Proceedings
Number of pages15
ISBN (Print)3540373764, 9783540373766
StatePublished - 2006
Event17th International Conference on Concurrency Theory, CONCUR 2006 - Bonn, Germany
Duration: Aug 27 2006Aug 30 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4137 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other17th International Conference on Concurrency Theory, CONCUR 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Minimization, learning, and conformance testing of boolean programs'. Together they form a unique fingerprint.

Cite this