Higher-Order MSL Horn Constraints
Higher-Order MSL Horn Constraints
复制标题
高阶 MSL 喇叭约束
DOI：
10.1145/3571262
复制
发表时间：
2023
影响因子：
--
通讯作者：
Jochems J
中科院分区：
文献类型：
--
作者：
Jochems J
一元浅线性（MSL）类是一阶Horn子句的可判定片段，在世纪之交被发现和重新发现，并应用于静态分析和验证。我们提出了一类新的高阶Horn约束，将MSL扩展到高阶逻辑，并开发了一个基于分辨率的决策过程。高阶MSL Horn约束可以很自然地捕获高阶程序中可能存在的调用和返回的复杂模式，这使得它们非常适合高阶程序验证。事实上，我们证明了高阶MSL可满足性问题和HORS模型检查问题是可互约的，因此高阶MSL可以被视为高阶模型检查的基于约束的方法。最后，我们描述了我们的决策过程及其应用程序验证套接字编程的实现。
The monadic shallow linear (MSL) class is a decidable fragment of first-order Horn clauses that was discovered and rediscovered around the turn of the century, with applications in static analysis and verification. We propose a new class of higher-order Horn constraints which extend MSL to higher-order logic and develop a resolution-based decision procedure. Higher-order MSL Horn constraints can quite naturally capture the complex patterns of call and return that are possible in higher-order programs, which make them well suited to higher-order program verification. In fact, we show that the higher-order MSL satisfiability problem and the HORS model checking problem are interreducible, so that higher-order MSL can be seen as a constraint-based approach to higher-order model checking. Finally, we describe an implementation of our decision procedure and its application to verified socket programming.
登录
查看更多内容
HFL 模型检查项目概述
影响因子：
--
作者：
Hyuno Kim;Yuji Yamakawa;Masatoshi Ishikawa;Kobayashi Naoki
通讯作者：
Kobayashi Naoki
DOI：
--
发表时间：
2009
期刊：
Proceedings of the 36th ACM SIGPLAN-SIGACT Symposium on principles of Programming Languages (POPL 2009)
影响因子：
--
作者：
Naoki Kobayashi;Types and Higher-Order
通讯作者：
Types and Higher-Order
证明相关的核心递归解析
DOI：
--
发表时间：
2015
期刊：
Fuji International Symposium on Functional and Logic Programming
影响因子：
--
作者：
Peng Fu;Ekaterina Komendantskaya;Tom Schrijvers;Andrew Pond
通讯作者：
Andrew Pond
HMC：使用抽象解释器验证功能程序
DOI：
--
发表时间：
2010
期刊：
International Conference on Computer Aided Verification
影响因子：
--
作者：
Ranjit Jhala;R. Majumdar;A. Rybalchenko
通讯作者：
A. Rybalchenko
可折叠下推自动机和递归方案
DOI：
10.1145/3091122
发表时间：
2008
期刊：
2008 23rd Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
M. Hague;A. Murawski;C. Ong;O. Serre
通讯作者：
O. Serre