Abstract:
Discrete event systems (DES's) are well established models in what can now be con-
sidered their traditional applications such as manufacturing systems, air tra c and other
transportation systems, and computer networks [1, 2].
The problem of discrete controller design is of increasing signi cance. Embedded sys-
tems, for example, commonly have both \high level" discrete digital controllers and \low
level" analog systems. Other examples include monitoring and control systems for automo-
biles and large buildings, pacemakers, and autonomous vehicles [1, 3, 4].
Control engineering has traditionally emphasized analog systems, but is increasingly
treating the discrete part as a genuine control problem and not simply an exercise in mi-
crocontroller programming. For example, the Supervisory Control Theory of DES's [5] is
a continuing research area, as is the general problem of hybrid control [6], in which the
discrete and analog parts must be designed jointly.
Analog control theory includes system identi cation as an important topic. The iden-
ti cation of DES in the form of nite automata also has an extensive literature. However,
on the problem of timed discrete event system identi cation, the literature is almost silent.
The models yielded by identi cation are important for control design and also in their
own right. Such a model can be used to analyze or simulate the behavior of a system in
some context, such as its interaction with a proposed controller design, or as a component
in a system-of-systems.
DES models can be arrived at by analysis (i.e., in terms of internal components), or
simply by assuming a certain structural form. However, when internals are inaccessible
or when analysis is relatively di cult or expensive (e.g., in the case of a legacy system
that was left undocumented, or the reverse-engineering of a competitor's product), model
identi cation could be useful.
This dissertation describes the investigation and evaluation of a novel approach to iden-
ti cation of timed discrete event systems. The main results are a discrete-event systems
formalism amenable to identi cation, and the identi cation algorithm itself. Simulation re-
sults are given that illustrate performance under both best-case and worst-case identi cation
conditions.
