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.

This is joint work with Hichem Lamouchi.