We study the expressivity and complexity of model checking linear temporal logic with team semantics (TeamLTL). TeamLTL, despite being a purely modal logic, is capable of defining hyperproperties, i.e., properties which relate multiple execution traces. TeamLTL has been introduced quite recently and only few results are known regarding its expressivity and its model checking problem. We relate the expressivity of TeamLTL to logics for hyperproperties obtained by extending LTL with trace and propositional quantifiers (HyperLTL and HyperQPTL). By doing so, we obtain a number of model checking results for TeamLTL and identify its undecidability frontier. In particular, we show decidability of model checking of the so-called left-flat fragment of any downward closed TeamLTL-extension. Moreover, we establish that the model checking problem of TeamLTL with Boolean disjunction and inclusion atoms is undecidable.
翻译:我们研究了与小组语义学(TeamLTL)进行线性时间逻辑检查模型的表达性和复杂性。TeamLTL尽管是一种纯粹的模式逻辑,但能够界定超异性,即与多处处决痕迹有关的属性。TeamLTL最近才引入了TeamLTL,其表达性和模式检查问题方面鲜为人知。我们把TeamLTL的表达性与通过将LTL与痕量和假设量化符(HyperLTL和HyperQPTL)扩大而获得的超超异性逻辑(TeamLTLT)的逻辑联系起来。通过这样做,我们获得了TeamLTL(TLT)的一些模式检查结果,并确定了其不可改变的边界。特别是,我们展示了对任何向下关闭的TechLTLTExext的所谓左减缩碎片进行示范检查的可变性。此外,我们确定TegLTL与Boolean断合和包容原子的模型无法确定。