Towards the exact complexity of realizability for Safety LTL
We study the realizability and strong satisfiability problems for SAFETY LTL, a syntactic fragment of Linear Temporal Logic ([Formula presented]) capturing safe formulas. While it is well-known that realizability for this fragment lies in [Formula presented], the best-known lower bound is [Formula presented]-hardness. Surprisingly, closing this gap has proven an elusive task. Previous works have c