We study best-effort synthesis under environment assumptions specified in LTL, and show that this problem has exactly the same computational complexity of standard LTL synthesis: 2EXPTIME-complete. We provide optimal algorithms for computing best-effort strategies, both in the case of LTL over infinite traces and LTL over finite traces (i.e., LTLf). The latter are particularly well suited for implementation.
Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up / Aminof, Benjamin; DE GIACOMO, Giuseppe; Rubin, Sasha. - In: IJCAI. - ISSN 1045-0823. - (2021), pp. 1766-1772. (Intervento presentato al convegno Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021 tenutosi a Montreal, Canada) [10.24963/ijcai.2021/243].
Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up
Giuseppe De Giacomo
;
2021
Abstract
We study best-effort synthesis under environment assumptions specified in LTL, and show that this problem has exactly the same computational complexity of standard LTL synthesis: 2EXPTIME-complete. We provide optimal algorithms for computing best-effort strategies, both in the case of LTL over infinite traces and LTL over finite traces (i.e., LTLf). The latter are particularly well suited for implementation.| File | Dimensione | Formato | |
|---|---|---|---|
|
Aminof_Best-Effort Synthesis_2021.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
160.31 kB
Formato
Adobe PDF
|
160.31 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
