Testing and Checking of Finite State Systems

Finite state achines have been used to model a wide variety of systems, including sequential circuits, communication protocols, and other types of reactive systems, i.e., systems that interact with their environment. In testing problems we are given a system, which we may test by providing inputs and observing the outputs produced. The goal is to design test sequences so that we can deduce desired information about the given system under test, such as whether it imple- ments correctly a given specification machine (conformance testing), or whether it satisfies given requirement properties (black-box checking).

In this talk we will review some of the theory and algorithms on basic testing problems for systems odeled by different types of finite state achines. Conformance testing of deter inistic achines has been investigated for a long time; we will discuss various efficient ethods. Testing of nondeter inistic and probabilistic achines is related to games with incomplete infor ation and to partially observable Markov decisions processes.

Authors and Affiliations

1. Avaya Laboratories, 07920, Basking Ridge, NJ, USA

   Mihalis Yannakakis

Editors and Affiliations

1. Compaq Cambridge Research Laboratory, One Cambridge Center, 02142-1612, Cambridge, MA, USA

   Sergio Rajsbaum

Reprints and permissions

© 2002 Springer-Verlag Berlin Heidelberg

Policies and ethics