2004 Milner Lecture
Testing, Optimization and Games
Mihalis Yannakakis
5.15 pm, George Square Lecture Theatre
As systems become larger and more complex, there
is a growing need for the development of effective automated
methods to test them to ensure their correct functioning.
We will discuss algorithmic problems arising
in the testing of reactive systems
(i.e. systems that interact with their environment),
modeled by various types of state machines.
The goal is to design test sequences so
that we can deduce desired information about the given system
under test, such as whether it conforms to a given
specification model, or whether it satisfies
given requirement properties.
Test generation can be approached from different points
of view - as an optimization problem of minimizing cost
and maximizing the effectiveness of the tests; as a game
between tester and system under test; or as a learning problem.
We touch on some of these aspects and related algorithmic questions.
