Controllers for discrete event systems via morphisms

P. Madhusudan, P. S. Thiagarajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study the problem of synthesising controllers for discrete event systems. Traditionally this problem is tackled in a linear time setting. Moreover, the desired subset of the computations of the uncontrolled system (often called a plant) is specified by automata theoretic means. Here we formulate the problem in a branching time framework. We use a class of labelled transition systems to model both the plant and the specification. We deploy behaviour preserving morphisms to capture the role of a controller; the controlled behaviour of the plant should be related via a behaviour preserving morphism to the specification at the level of unfoldings. One must go over to unfoldings in order to let the controller use memory of the past to carry out its function. 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 the size of the finite controller, if one exists can be bounded by a polynomial in the sizes of the plant and the specification. Such a controller can also be effectively constructed. We then prove that in a natural concurrent setting, the problem of checking for the existence of a (finite) controller is undecidable.

Original languageEnglish (US)
Title of host publicationCONCUR 1998 Concurrency Theory - 9th International Conference, Proceedings
EditorsDavide Sangiorgi, Robert de Simone
Number of pages16
ISBN (Print)9783540648963
StatePublished - 1998
Externally publishedYes
Event9th International Conference on Concurrency Theory, CONCUR 1998 - Nice, France
Duration: Sep 8 1998Sep 11 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Concurrency Theory, CONCUR 1998

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Controllers for discrete event systems via morphisms'. Together they form a unique fingerprint.

Cite this