243@2021@IJCAI

#1 Best-Effort Synthesis: Doing Your Best Is Not Harder Than Giving Up [PDF] [Copy] [Kimi] [REL]

Authors: Benjamin Aminof ; Giuseppe De Giacomo ; Sasha Rubin

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.