@inproceedings{CJB+11,
title = {On the Hardness of Priority Synthesis },
author = {Cheng, Chih-Hong and Jobstmann, Barbara and Buckl, Christian and Knoll, Alois},
year = {2011},
booktitle = {Implementation and Application of Automata - 16th International Conference, CIAA 2011, Blois, France, July 13-16, 2011. Proceedings},
pages = {110-117},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {6807},
team = {DCS},
abstract = {We study properties of priority synthesis, an automatic method to ensure desired safety properties in component-based systems using priorities. Priorities are a powerful concept to orchestrate components, e.g., the BIP4 framework for designing and modeling embedded and autonomous systems is based on this concept.
We formulate priority synthesis for BIP systems using the automata-theoretic framework proposed by Ramadge and Wonham. In this framework, priority synthesis results in searching for a supervisor from the restricted class of supervisors, in which each is solidly expressible using priorities. While priority-based supervisors are easier to use, e.g., they support the construction of distributed protocols, they are harder to compute. In this paper, we focus on the hardness of synthesizing priorities and show that finding a supervisor based on priorities that ensures deadlock freedom of the supervised system is NP-complete.
},
}
