专栏首页arxiv.org翻译专栏不动点方程组的抽象、技巧与对策
原创

不动点方程组的抽象、技巧与对策

在本文中,我们介绍了不动点方程组的抽象、技巧与对策,由(混合的)最小和最大的固定点方程组成的完整晶格上的固定点方程系统允许一个人表达一些验证任务,例如各种规格逻辑的模型检查或协导行为等价的检查。 在本文中,我们发展了一种抽象解释式的定点方程系统的近似理论:在一个合适的抽象域中,将一个特定域上的系统抽象到一个系统中,条件保证了抽象解表示具体解的一个健全/完全的过度近似。 有趣的是,直到技术,一种经典的方法,用于协导设置,以获得更容易或可行的证明,可以解释为抽象的方式,它们自然适合于我们的框架,并扩展到方程组。 此外,依靠近似理论,我们可以提供一个描述在一个合适的奇偶博弈上的完全晶格上的固定点方程组的解,概括了最近一些仅限于连续晶格的工作。 游戏视图为动态算法的发展开辟了道路,以表征这种方程系统的解。

原文题目:Abstraction, Up-to Techniques and Games for Systems of Fixpoint Equations

原文:Systems of fixpoint equations over complete lattices, consisting of (mixed) least and greatest fixpoint equations, allow one to express a number of verification tasks such as model-checking of various kinds of specification logics or the check of coinductive behavioural equivalences.

In this paper we develop a theory of approximation for systems of fixpoint equations in the style of abstract interpretation: a system over some concrete domain is abstracted to a system in a suitable abstract domain, with conditions ensuring that the abstract solution represents a sound/complete overapproximation of the concrete solution.

Interestingly, up-to techniques, a classical approach used in coinductive settings to obtain easier or feasible proofs, can be interpreted as abstractions in a way that they naturally fit in our framework and extend to systems of equations.

Additionally, relying on the approximation theory, we can provide a characterisation of the solution of systems of fixpoint equations over complete lattices in terms of a suitable parity game, generalising some recent work that was restricted to continuous lattices.

The game view opens the way to the development of on-the-fly algorithms for characterising the solution of such equation systems.

原文作者:Paolo Baldan,Barbara König,Tommaso Padoan

原文地址:https://arxiv.org/abs/2003.08877

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于PfSPZ的疟疾疫苗生产的蚊子取放系统(CS RO)

    疟疾的治疗是一项全球性的健康挑战,而从该疾病的疫苗的广泛引入中受益匪浅。已经开发出一种利用寄生虫恶性疟原虫(Pf)的子孢子(SPZ)制备活体生物疫苗的方法,该子...

    时代在召唤
  • 利用可微物理模拟学习滑动中的未知物体(CS RO)

    提出了一种将未知目标从初始配置推送到具有稳定性约束的目标配置的新方法。该方法利用可微物理模型的最新进展来学习被推物体的未知力学性质,如其质量分布和摩擦系数。所提...

    时代在召唤
  • GAN和微分轨迹栅格化:改进鸟瞰模型中交通参与者的运动预测(CS RO)

    自动驾驶难题的最关键部分之一是预测周围交通参与者的未来运动的任务,这使自动驾驶汽车能够安全有效地规划复杂世界中的未来路线。最近,在工业界和学术界的研究人员日益增...

    时代在召唤
  • 形状变换在地震、风浪数据时间序列分类中的应用(CS LG)

    由于对大量工程结构(包括建筑物、桥梁、塔楼和海上平台等)的长期健康监测,使用时间序列分类法从大型数据库中自主检测所需事件,在土木工程中越来越重要。在这种情况下,...

    刘持诚
  • 亚马逊DRKG使用体验

    基于文章:探索「老药新用」最短路径:亚马逊AI Lab开源大规模药物重定位知识图谱DRKG,记录了该项目的实际部署与探索过程,供参考。

    Bo_hemian
  • deepmind 做通用人工智能的思路

    Automated discovery of early visual concepts from raw image data is a major open...

    用户1908973
  • 部署机器学习以帮助数字人性化:提高OpenStreetMap中的图像注释效率(CS HC)

    在发展中国家的农村地区进行人口定位吸引了人性化绘图项目的关注,因为规划措施对脆弱地区的影响很大。最近的努力已经解决了这个问题,即在空中图像中检测建筑物。但是,像...

    用户7724223
  • 人工智能的回报率:对冲基金嵌入机器学习?

    ARTIFICIAL intelligence (AI) has already changed some activities, including part...

    企鹅号小编
  • 关于对称直线矩阵划分 (CS)

    在许多应用程序中,均匀地将不规则的工作负载分配到处理单元是实现高效并行的关键。在这项工作中,我们关注稀疏矩阵的一种称为直线分区(也称为广义块分布)的空间划分。更...

  • 动态多智能体系统中强化学习模型的解释(CS)

    译文:近年来,人们对深度强化学习(DRL)系统的透明度和可解释性越来越感兴趣。口头解释作为我们日常生活中最自然的交流方式,更值得关注,因为它可以让用户更好地了解...

    N乳酸菌

扫码关注云+社区

领取腾讯云代金券