From Linear Systems to Discrete-Event Systems

[Talk presented at various institutions, 2006]

W.M. Wonham
Systems Control Group
ECE Department
University of Toronto

ABSTRACT

In this talk we trace the development of a control theory of discrete-event
systems (DES), first proposed around 1983 and still an active area of
research.  The general concepts underlying modern control theories - 
optimality, controllability, and observability - had arisen during the
1940s-'60s, notably in the approaches to linear system synthesis pioneered by
Wiener, Krasovskii, Kalman and others.  Perhaps surprisingly, the adaptation
of these concepts to the seemingly quite different setting appropriate to DES
 - automata and formal languages - proved to be relatively straightforward,
especially on the analogy of ideas from geometric linear control (like
subspace ordering) that had emerged in the 1960s and '70s.  Until fairly
recently, the application of DES control theory to problems of realistic
industrial size has been inhibited by exponential state-space explosion.
However, we can now report some success in confronting exponentiality through
effective control architecture - for instance an adaptation of state charts -
combined with symbolic computing techniques involving binary or integer
decision diagrams.  In these approaches it is often essential to identify
'natural' modular system structure as the point of departure.  A continuing 
challenge, however, is how to 'steer' a formal synthesis towards a common-
sense simple and comprehensible solution when the latter happens to exist.

____________________________________________________________________________



