Games for Efficient Supervisor Synthesis

In recent years, there was an increasing interest in the connections between supervisory control theory and reactive synthesis. As the two fields use similar techniques there is great hope that technologies from one field could be used in the other. In this spirit, we provide an alternative reduction from the supervisor synthesis problem to solving B\"uchi games via games with a non-blocking objective. Our reduction is more compact and uniform than previous reductions. As a consequence, it gives an asymptotically better upper bound on the time complexity of the supervisory control synthesis problem. Our reduction also breaks a widely held belief about the impossibility of reduction of supervisory control synthesis problem to a game with linear winning condition. Contributed talk given by Prabhat Kumar Jha

Authors

• Prabhat Kumar Jha

Keywords

No keywords are indexed for this paper.