On the Expressivity of RoCTL*

RoCTL * was proposed to model robustness in concur-rent systems. RoCTL * extended CTL * with the addition of Obligatory and Robustly operators, which quantify over failure-free paths and paths with one more failure respec-tively. Whether RoCTL * is more expressive than CTL * has remained an open problem since the RoCTL * logic was proposed. We use the equivalence of LTL to counter-free automata to show that RoCTL * is expressively equivalent to CTL*; the translation to CTL * provides the first model checking procedure for RoCTL*. However, we show that RoCTL * is relatively succinct as all satisfaction preserving translations into CTL * are non-elementary in length. Draft