On the Hardness of Priority Synthesis

Abstract. We study properties of priority synthesis [2], an automatic method to ensure desired safety properties in component-based systems using priorities. Priorities are a powerful concept to orchestrate com-ponents [3], e.g., the BIP1 framework [1] 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 [5]. 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 prior-ities and show that finding a supervisor based on priorities that ensures deadlock freedom of the supervised system is NP-complete.