Cheap CTL Compassion in NuSMV. We discuss expansions of (mathsf CTL) with connectives able to express Streett fairness objectives for single paths. We focus on (mathsf (E)SFCTL): (Extended) StreettFair (mathsf CTL) inspired by a seminal paper of Emerson and Lei. Unlike several other fair extensions of (mathsf CTL), our entire formalism (not just a subclass of formulas in some canonical form) allows a succinct embedding into the (mu )calculus, while being able to express concisely all relevant types of pathbased fairness objectives. We implement our syntax in the wellknown symbolic model checker NuSMV, consequently also implementing (mathsf CTL) model checking with xe2x80x9ccompassionxe2x80x9d objectives. Since the (mu )calculus embedding requires only alternation depth two, the resulting specifications correspond to parity games with two priorities. This allows a comparison of the performance of our NuSMV(mathsf sf) with existing parity game solvers (both explicit and symbolic). The advantages of the symbolic approach seem to extend to fair model checking.

The Keys to Decidable HyperLTL Satisfiability: Small Models or Very Simple Formulas HyperLTL, the extension of Linear Temporal Logic by trace quantifiers, is a uniform framework for expressing information flow policies by relating multiple traces of a securitycritical system. HyperLTL has been successfully applied to express fundamental security policies like noninterference and observational determinism, but has also found applications beyond security, e.g., distributed protocols and coding theory. However, HyperLTL satisfiability is undecidable as soon as there are existential quantifiers in the scope of a universal one. To overcome this severe limitation to applicability, we investigate here restricted variants of the satisfiability problem to pinpoint the decidability border. First, we restrict the space of admissible models and show decidability when restricting the search space to models of bounded size or to finitely representable ones. Second, we consider formulas with restricted nesting of temporal operators and show that nesting depth one yields decidability for a slightly larger class of quantifier prefixes. We provide tight complexity bounds in almost all cases.