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断合和包容原子的模型无法确定。

0
下载
关闭预览

相关内容

【KDD2021】图神经网络,NUS- Xavier Bresson教授
专知会员服务
64+阅读 · 2021年8月20日
元学习与图神经网络逻辑推导,55页ppt
专知会员服务
129+阅读 · 2020年4月25日
因果图,Causal Graphs,52页ppt
专知会员服务
248+阅读 · 2020年4月19日
Python数据分析:过去、现在和未来,52页ppt
专知会员服务
101+阅读 · 2020年3月9日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
104+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年1月27日
Arxiv
0+阅读 · 2022年1月25日
Arxiv
3+阅读 · 2021年11月1日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员