Branching time controllers for discrete event systems

Madhusudan, P. ; Thiagarajan, P. S. (2002) Branching time controllers for discrete event systems Theoretical Computer Science, 274 (1-2). pp. 117-149. ISSN 0304-3975

Full text not available from this repository.

Official URL:

Related URL:


We study the problem of synthesizing controllers for discrete event systems in a branching time framework. We use a class of labelled transition systems to model both plants and specifications. We use first simulations and later bisimulations to capture the role of a controller; the controlled behaviour of the plant should be related via a simulation (bisimulation) to the specification. For both simulations and bisimulations we show that the problem of checking if a pair of finite transition systems - one modelling the plant and the other the specification - admits a controller is decidable in polynomial time. We also show that the size of the controller, if one exists, can be bounded by a polynomial in the sizes of the plant and the specification and can be effectively constructed in polynomial time. Finally, we prove that in the case of simulations, the problem of checking for the existence of a controller is undecidable in a natural concurrent setting.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Discrete-event Systems; Controller Synthesis; Supervisor Synthesis; Simulations; Bisimulations; Asynchronous Transition Systems
ID Code:50515
Deposited On:25 Jul 2011 11:44
Last Modified:25 Jul 2011 11:44

Repository Staff Only: item control page