Supervisory Control of Discrete Event Systems with CTL* Temporal Logic Specifications

Abstract

The supervisory control problem of discrete event systems with temporal logic specifications is studied. The full branching time logic of CTL* is used for expressing specifications of discrete event systems. The control problem of CTL* is reduced to the decision problem of CTL*. A small model theorem for the control of CTL* is obtained. It is shown that the control problem of CTL* (resp., CTL) is complete for deterministic double (resp., single) exponential time. A sound and complete supervisor synthesis algorithm for the control of CTL* is provided. Special cases of the control of computation tree logic (CTL) and linear-time temporal logic are also studied.