The Complexity of LTL Rational Synthesis
- Open Access
- 2022
- OriginalPaper
- Buchkapitel
- Verfasst von
- Orna Kupferman
- Noam Shenwald
- Verlag
- Springer International Publishing
Zusammenfassung
In rational synthesis, we automatically construct a reactive system that satisfies its specification in all rational environments, namely environments that have objectives and act to fulfill them. We complete the study of the complexity of LTL rational synthesis. Our contribution is threefold. First, we tighten the known upper bounds for settings that were left open in earlier work. Second, our complexity analysis is parametric, and we describe tight upper and lower bounds in each of the problem parameters: the game graph, the objectives of the system components, and the objectives of the environment components. Third, we generalize the definition of rational synthesis, combining the cooperative and non-cooperative approaches studied in earlier work, and extend our complexity analysis to the general definition.
- Titel
- The Complexity of LTL Rational Synthesis
- Verfasst von
-
Orna Kupferman
Noam Shenwald
- Copyright-Jahr
- 2022
- Buch
-
Tools and Algorithms for the Construction and Analysis of Systems
Print ISBN: 978-3-030-99523-2
Electronic ISBN: 978-3-030-99524-9
Copyright-Jahr: 2022
- DOI
- https://doi.org/10.1007/978-3-030-99524-9_2
