Games for Efficient Supervisor Synthesis

In recent years, there has been 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 red...

Full description

Saved in:
Bibliographic Details
Published in:IEEE control systems letters 2023-01, Vol.7, p.1-1
Main Authors: Hausmann, Daniel, Jha, Prabhat Kumar, Piterman, Nir
Format: Article
Language:English
Subjects:
Computer Science
Datavetenskap (datalogi)
Discrete event systems
Encoding
Forestry
Game theory
Games
Runtime
Software algorithms
Supervisory control
Upper bound
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years, there has been 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üchi 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 reducing the supervisory control synthesis problem to a game with a linear winning condition.
ISSN:2475-1456
2475-1456
DOI:10.1109/LCSYS.2023.3290727