Eager: Optimal Length Integer Resolution Refutation in UTVPI Constraints
Eager: Optimal Length Integer Resolution Refutation in UTVPI Constraints
批准号:
1305054
负责人:
Krishnamurthy Subramani
金额:
$6.57万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2013
资助国家:
美国
项目状态:
已结题
起止时间:
2013-07-01 至 2016-06-30
中文摘要
约束求解是程序验证的一个组成部分,一般来说,特别是抽象解释。本文探讨了一类特殊约束的整数可行性检验和证明的基本问题,称为单位二变量每不等式(UTVPI)约束。这种方法基于对整数可行性检查问题的全新见解,并将提供不可行性的实际证明。提供正面和负面证书的能力将影响程序验证,并增强软件的可靠性。本课题使用的FMR (Fourier-Motzkin with舍入)证明体系,是建立UTVPI系统格点不可行性的完善体系。这项工作将通过适当定义的大小概念隔离FMR证明系统中最小尺寸的不可行性证明,并将通过尝试识别证书的形式和优化此类证书的大小来探索认证问题。
英文摘要
Constraint solving is an integral part of program verification, in general and abstract interpretation in particular. This proposal exploressome fundamental issues in integer feasibility checking and certification for a specialized class of constraints called Unit Two Variable Per Inequality (UTVPI) constraints. This approach is based on fundamentally new insights into the problem of integer feasibility checking, and will provide actual certificates of infeasibility. The ability to provide positive and negative certificates will impact program verification, and enhance the reliability of software.This project uses a proof system called FMR (Fourier-Motzkin with Rounding), which is a sound and complete system for establishing the lattice point infeasibility of a UTVPI system. This work will isolate the smallest-sized proof of infeasibility in the FMR proof system with an appropriately defined notion of size, and will explore the problem of certification by trying to identify the form of certificates and optimize the size of such certificates.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Polyhedral Approaches to Selected Problems in Computational Logic
-
批准号:0827397
-
项目类别:Standard Grant
-
资助金额:$30.03万
-
财政年份:2009
-
负责人:Krishnamurthy Subramani
-
依托单位:
Collaborative Research: Algorithmic Aspects of Risk Management
-
批准号:0849735
-
项目类别:Standard Grant
-
资助金额:$13.47万
-
财政年份:2009
-
负责人:Krishnamurthy Subramani
-
依托单位:
海外基金