While most approaches in formal methods address system correctness, ensuring robustness has remained a challenge. In this paper we present and study the logic rLTL which provides a means to formally reason about both correctness and robustness in system design. Furthermore, we identify a large fragment of rLTL for which the verification problem can be efficiently solved, i.e., verification can be done by using an automaton, recognizing the behaviors described by the rLTL formula $\varphi$, of size at most $\mathcal{O} \left( 3^{ |\varphi|} \right)$, where $|\varphi|$ is the length of $\varphi$. This result improves upon the previously known bound of $\mathcal{O}\left(5^{|\varphi|} \right)$ for rLTL verification and is closer to the LTL bound of $\mathcal{O}\left( 2^{|\varphi|} \right)$. The usefulness of this fragment is demonstrated by a number of case studies showing its practical significance in terms of expressiveness, the ability to describe robustness, and the fine-grained information that rLTL brings to the process of system verification. Moreover, these advantages come at a low computational overhead with respect to LTL verification.


翻译:虽然在正式方法中,大多数方法都涉及系统正确性,但确保稳健性仍然是一项挑战。在本文件中,我们提出并研究rLTL逻辑,它提供了一种手段,正式说明系统设计是否正确和稳健性。此外,我们确定了一个大块rLTL的碎片,可以有效解决核查问题,即核查可以通过使用一个自动图进行,承认rLTL公式所描述的大小最多为$\phal{O}/left(3 ⁇ ⁇ varphi ⁇ \right)美元的行为。一些案例研究表明,美元是美元,是美元,是美元,是美元,是美元,是系统长度,是美元,是用来正式说明准确性。此外,这种结果改进了以前已知的RLT的界限,是用于核查的5 ⁇ varphi{\\right$,更接近LT的束缚值。

0
下载
关闭预览

相关内容

【PAISS 2021 教程】概率散度与生成式模型,92页ppt
专知会员服务
33+阅读 · 2021年11月30日
[CVPR 2021] 序列到序列对比学习的文本识别
专知会员服务
28+阅读 · 2021年4月14日
专知会员服务
22+阅读 · 2021年4月10日
专知会员服务
50+阅读 · 2020年12月14日
最新《深度卷积神经网络理论》报告,35页ppt
专知会员服务
45+阅读 · 2020年11月30日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【音乐】Attention
英语演讲视频每日一推
3+阅读 · 2017年8月22日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Decomposing Natural Logic Inferences in Neural NLI
Arxiv
0+阅读 · 2021年12月15日
Arxiv
0+阅读 · 2021年12月15日
Arxiv
0+阅读 · 2021年12月14日
Arxiv
0+阅读 · 2021年12月13日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Neural Arithmetic Logic Units
Arxiv
5+阅读 · 2018年8月1日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【音乐】Attention
英语演讲视频每日一推
3+阅读 · 2017年8月22日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Decomposing Natural Logic Inferences in Neural NLI
Arxiv
0+阅读 · 2021年12月15日
Arxiv
0+阅读 · 2021年12月15日
Arxiv
0+阅读 · 2021年12月14日
Arxiv
0+阅读 · 2021年12月13日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Neural Arithmetic Logic Units
Arxiv
5+阅读 · 2018年8月1日
Top
微信扫码咨询专知VIP会员