← All problems
Unverified

SafeLTL

An ω\omega-word language L⊆ΣωL\subseteq \Sigma^\omega is a safety language if for all w∉Lw\not \in L there is a prefix v∈Σ∗v\in \Sigma^* of ww such that for all u∈Σωu\in \Sigma^\omega, vu∉Lvu\not \in L. safeLTL is the fragment of negation normal form LTL without Until nor Finally. SafeLTL captures exactly LTL expressible safety properties. However, to go from an LTL formula describing a safety property to an equivalent safeLTL formula, the best known translation seems to go via a deterministic safety automaton and then back to LTL, incurring a triple-exponential blow-up on the way. Open problem: Is there a (more) concise translation from LTL to safeLTL? Are there safety properties that are exponentially more concisely expressible in LTL than safeLTL?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu