Control of infinite behaviour of discrete event systems
under partial observations
John Thistle
Department of Electrical and Computer Engineering
'Ecole Polytechnique de Montreal
thistle@auto.polymtl.ca
Language-based studies of discrete event systems control
are typically carried out within a framework of finite event
strings. The extension to infinite strings allows the expression
of a broader range of system properties, and connects discrete
event control with related work in computer science and logic.
This seminar will first present the solution of a centralized
control problem under partial observations, where the
plant and specification are represented as finite automata
on infinite strings. Computationally, partial observations
entail the replacement of a nondeterministic automaton
(or more precisely, a universal, or ``forall'' automaton) with
an equivalent deterministic one. While ``determinization''
of automata on infinite strings is generally much more
involved than the finite-string procedure, some mild
assumptions allow the use of the classical subset construction,
which can then be used to reduce the partial observations
problem to one of complete observations. On the other hand,
a decentralized version of the problem is undecidable. This
last result carries over to the finite-string case.