没有合适的资源?快使用搜索试试~ 我知道了~
--理论计算机科学电子笔记269(2011)3-17www.elsevier.com/locate/entcs基于DPLL的可满足性求解器1纳塔拉詹·尚卡尔计算机科学实验室美国加州门洛帕克94025csl.sri.com网址:http://www.csl.sri.com/马克·沃谢E'colePolytechniquemarc.polytechnique.org摘要近年来,命题满足性过程或SAT求解器的能力有了显著的提高。加速是众多优化的结果,包括冲突导向的backjumping。我们使用原型验证系统(PVS)来验证基于以下内容的满足性程序:Davis-Putnam-Logemann-Loveland(DPLL)方案具有这些优化。 这次演习是 这是验证满足性程序有效实施的一个步骤。 我们的验证SAT求解器是一个更大的研究计划的一部分,为使用一个经过验证的参考内核,包含一个经过验证的SAT求解器。 我们的验证利用PVS中的谓词子类型和依赖类型来捕获规范和关键不变量。关键词:SAT求解器,回集,谓词子类型,依赖类型,PVS1介绍推理过程在编程和其他学科中有许多重要的应用。近年来,推理程序的能力和效率有了快速的发展,特别是在求解比例满足性(SAT)和满足性模理论(SMT)的过程中。这些过程用于断言验证、有界模型检查、无界模型检查和规划。除了使这些程序有效外,[1]本论文完成于2008年夏天,当时第二作者正在巴黎高等理工学院学习。 他现在在巴黎的一家公司工作。本工作得到了NSFGran ntsCSR-EHCS(CPS)-0834810和CNS-0917375以及NASA合作协议NNX 08 AY 53 A的支持。1571-0661 © 2011由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2011.03.0024N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3强大的,我们有兴趣在理论上更深入地了解如何以及为什么这些程序的工作。这种理解可以导致更有效的推理过程。它也可以用来实现对计算正确性的显著信任,而不会通过使用在线验证的参考实现来检查在线不可信过程的结果来限制其效率[17]。作为构建此类验证参考的一步,我们描述了使用原型验证系统(PVS)[ 13 ]基于Davis-Putnam-Logemann-Loveland方法[ 9,6 ]的抽象SAT求解器的我们的工作属于机械化核查工作的长期传统, 元理论程序许多早期的结果是由Boyer和Moore使用他们著名的定理证明器[1]实现的。这些例子包括麦卡锡-画家证明编译器对算术表达式的正确性,满足性求解器对条件表达式的正确性,以及纯Lisp的图灵完备性[2]。Shankar [14]描述了命题逻辑的可靠性、完备性和可判定性(通过满足性求解器)的证明,以及无类型lambda演算的Church-Rosser定理[ 15 ]和哥德尔不完备性定理[ 16 ]的证明从那时起,各种各样的决策程序在各种各样的系统中得到了机械的验证。其中一些甚至被用于自动化证明。在过去的十年中,命题满足性程序已经变得非常强大,从SATO [20],GRASP [12]和Cha [11]等系统开始。由于这些改进,SAT求解器在硬件和软件验证、约束求解和测试生成中得到了广泛且不断增长的应用。现代SAT求解器效率的提高来自于使用巧妙的数据结构的快速布尔约束传播虽然我们对基于DPLL的SAT求解的处理有些抽象,但在我们的形式化中唯一不可执行的操作是变量选择操作,主要是因为这涉及启发式而不是逻辑考虑。我们的形式化包括子句学习和backjumping,但不包括布尔约束传播的两个文字观看方法。我们的验证是迈向验证完全可执行和有效的SAT求解器的第一步[11]。这样的SAT求解器构成了验证参考内核架构中的关键组件,可用于验证不可信的高度工程化证明工具的结果。可信SAT求解器可以用于验证其他不可信验证器的结果,例如二元决策图(BDD)[3],模型检查器[4]和SMT求解器[7]。SAT求解器的验证对机械化提出了重大挑战。我们的验证虽然是交互式的,但利用了PVS语言和推理机制的几个功能。特别是,我们使用PVS来交互式地探索形式化的细节,以便我们在这一点上的证明涉及到相当数量的手动指导。我们计划利用我们的发展来探索更大机械化的策略,特别是通过更多地使用命题可满足性和可满足性模理论的求解器N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)35i=12DPLL稳定性程序给定一组命题变量P,命题公式具有文法Φ:= P| ¬ Φ |Φ 1∨ Φ 2公式φ的赋值M将命题变量映射为真值{n,T}.令<$和对应于<$和连接词的真值表解释。公式φ关于赋值M的真值M[[φ]可以从连接词的真值表解释中计算出来。 如果M[[φ]] =T,则M是φ的模型。命题公式可以转化为等价合取范式(CNF)。字面量是命题变量p或其否定形式<$p。如果k是文字p(分别为<$p),则它的补k是<$p(分别为p)。子句κ是一个析取项k1<$... 其中n≥0,并且每个ki(1≤i≤n)都是文字。在不失一般性的情况下,我们假设子句不包含重复的文字,并且从不同时包含文字及其补集。合取式标准形式是一组子句。CNF公式nκi是满足的,如果它有模型 子句κ是子句集合K的后果,如果K的任何模型M也是一个模型。例如,推理的归结规则,其中子句κκJ是从子句k κ和k κ j导出的,并且是子句kκ和kκJ的结果。在非正式的介绍中,我们假设一个子句中文字的出现顺序是无关紧要的,可以自由排列。Davis-Putnam-Logemann-Loveland过程[ 9,6 ](DPLL)推理系统在m个比例变量[ 7 ]上搜索n个子句K的集合的满意赋值。它通过在水平l中建立部分赋值M和一组隐含的冲突引理C来实现这一点。一 个部分赋值M到第1层有M0;M1;. ;Ml.部分赋 值 M0是一个 对 ki[γi]的集合 ,其中 γi∈K <$C, 源子句γi来自K<$C。对于0 0时,应用分析过程构造一个相容引理θ.它通过反复地6N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3用用γJ解析γ的结果替换γ,其中k[γJ]出现在M中,并且k是出现在γ中的当前级别的文字(但不是唯一的这样的文字)。γ的新值在M中也是可证伪的,因为γJ的形式为k<$γJJ,其中γJJ在M中是可证伪的。当γ在当前水平上包含唯一的文字k时,则我们令相容引理θ为γ。由analyze构造的constructive引理θ具有k<$θJ的形式。设lJ是最低水平,其中lJ q,s<$$> p <$q,<$s<$p <$$>q,<$p<$r,<$q<$<$r}。由于没有单元(单个文字)子句,因此在0级没有隐含文字因此,我们选择一个未赋值的文字,在本例中s作为第1级的决策文字。同样,在级别1没有隐含的文字,我们选择一个未赋值的文字r作为级别2的决策现在,我们可以将来自输入子句<$q<$$>r的隐含文字<$q和来自输入子句p<$q的隐含文字p相加。在这一点上,传播识别出一个冲突,其中部分赋值M伪造了输入子句<$p<$q。通过用q替换<$p得到单位分句q来分析冲突。 由于空分句的最大水平是0,所以当将单位分句q添加到连接分句集合C时,回跳产生水平0处的部分赋值q。然后,传播从输入子句pq产生隐含文字p,从输入子句r的伪造。由于该冲突发生在0级,我们报告不满意。该过程的正确性可以通过观察每一步都保持M0KC的可满足性来确定,因此当在0级检测到冲突时,则M0KC必须是不可满足的,因此K必须是不可满足的。 如果M是一个全赋值,使得K中没有子句生成与M的冲突,则K必须是可满足的。该过程终止,因为在每一步中,mi=0 |n(m + 1)(m-i)向一个界限(m + 1)(m +1)增加。| ∗ (m +1)(m−i)increases toward a bound (m +1)(m +1).3PVS中DPLL的形式化PVS是一个基于高阶逻辑和交互式证明的规范和验证框架。PVS规范语言丰富了简单类型的高阶逻辑,包括谓词子类型、依赖类型、抽象数据集和协数据集、归纳定义、类型判断、参数理论和理论解释。PVS中的证明是通过结合各种强大的自动化工具(如布尔简化、地面决策过程、重写、符号模型检查、启发式量化器实例化和归纳)交互式地构造的。新的证明策略可以根据旧的策略定义,ΣN. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)37resolution [m:posnat]:December 2009..结束分辨率.步骤LMK Cγ选择s1;sK ∅选择r2;s;rK ∅传播2;s;r,r]K ∅传播2;s;r,<$q,p[p<$q]K ∅有争议的 2;s;r,<$q,pK ∅ 普什克分析0∅K Q后跳0q[ q]K Q传播0q,p[p q]K Q传播0q,p,r[<$ p<$ r]K Q有争议的 0q,p,rK Qq图1.一、具有输入{p<$q,<$p<$q,p<$$> q,s<$p <$q,<$s<$p<$$> q,<$p<$r,<$q<$r}的DPLL过程语言我们提供了PVS的具体特征的示例,因为这些特征在形式化中使用。PVS形式化包括推理归结规则的形式化、部分赋值的表示、形式化中使用的基本操作的定义以及三个didn't. 我们大量使用谓词子类型和依赖类型来捕获关键不变量使用这些类型进行类型检查会生成称为类型正确性条件(TCC)的证明义务我们只给出关键的定义。完整的形式化可从相应的作者。3.1决议归结推理规则在PVS理论(类型、常量和公式的声明的集合)中被引入和证明,PVS理论由可以出现在子句中的变量索引上的边界m在归结理论中,命题原子被建模为子区间[1,m ]中的整数,文字是整数的谓词子类型,包含原子a和它的否定-a。8N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3非重言式?(ll:list[literal]):bool=(FORALL k:NOT(member[literal](k,ll)ANDmember[literal](-k,ll)bclause:TYPE =(非重言式?)pclause?(k)(ll):bool=member[literal](k,ll);nclause?(k)(ll):bool= member[literal](-k,ll);oclause?(k)(ll):bool= NOT(pclause?(k)(ll)或nclause?(k)(ll));resolve(k)(kk:(pclause?(k))、(ll |nclause?(k)(ll)并兼容?(k,kk)(ll):(oclause?(k)) 为append(delete(k,kk),delete(-k,ll))atom:TYPE = subrange(1,m)a,b:VAR atomliteral:TYPE ={i:subrange(-m,m)|i/= 0}k,l:VAR文字由谓词子类型bclause给出的子句是一个不同义反复一个模型是一个(总)赋值,它是从原子到布尔布尔的函数类型。model:TYPE = [atom ->bool]M,N:VAR模型从句ll是肯定从句(pclause?)对于文字k,如果它包含k作为列表的成员,则否定子句(nclause?)如果它包含-k,并且如果它既不包含k也不包含-k,则是中性子句。子句ll与子句kk关于文字k相容,如果在kk中正出现且在ll中负出现的唯一文字是k本身。兼容?(k,kk)(ll):bool =(FORALL1:member[literal](l,kk)ANDmember[literal](-l,ll)暗示l = k)resolve操作将文字k上的归结推理应用于子句kk(其中k出现在正态)和子句ll(其与kk兼容并且其中k出现在负态)。 它返回一个相对于k是中性的子句,并且通过分别从kk和ll中删除所有出现的k和-k,并追加结果子句来获得。对归结理论进行类型检查产生了几个证明义务,其中关键的一个要求归结返回的结果是关于k中立的非重言式。我们需要resolve的主要性质是它的结果是子句kk和ll的一个推论。resolve_sat:LEMMA(FORALL(M:model,kk:(pclause?(k))、(ll |nclause?(k)(ll)并兼容?(k,kk)(ll):满足(M,kk)且满足(M,ll)隐含满足(M,resolve(k)(kk,ll))N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)39lookup(M,1):bool=(M(abs(1))IFF1> 0)clause_table:TYPE =[# numclause:upfrom(n),子句:[below(numclause)-> ne_bclause]#]3.2部分转让部分赋值建模是形式化中最棘手的部分。部分赋值必须由一系列水平l组成,其中l≥0。每个级别l >0包含一个决策文字和一个隐含文字序列。每个隐含的文字都有一个源子句,必须在前面的赋值中被证伪。我们用四个独立的构造来捕获部分赋值。第一个构造是上面的模型M,它是原子到布尔的总映射。第二个构造是一个计数器索引,它维护分配的原子数和从原子到子范围[0,index]的部分内射映射I如果对于某个变量I(a)= 0,则该变量未赋值。映射I是部分内射的,因为如果0/ =I(a)=I(b)= 0,则a=b。我们实际上需要I是部分双射的,这样对于每个i到索引,集合{ a}的基数|1 ≤I(a)≤i}就是i。第三个构造是对应于决策文字的原子的堆栈。这个决策堆栈必须按I排序,这样如果堆栈中原子a在原子b之下,则为0 0且(M(a)IFF k 0)ANDfalsifies(index,I,M,lm))(终例)测量长度(lk)k的下标是I(abs(k))。 中的文字列表上的递归子句用于计算子句的最大索引maxindex(index,I,lk)。另一个类似的递归计算子句lk中的最大文字maxliteral(index,I,lk)。索引i的最大级别maxlevel(index,I,ls,i)是ls中低于i的决策文字的最高索引,通过决策堆栈上的递归来计算。子句表K是一个依赖记录,其中字段条目10N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3现在我们可以描述部分赋值的最后一个剩余组件,它是源表src,它将原子映射到对应于子句(在子句表中)的子句索引,其中原子作为隐含的文字出现。后一个条件再次通过依赖类型化和谓词子类型化来确保。总之,PVS中的谓词子类型和依赖类型用于捕获与部分赋值关联的关键数据类型不变量3.3推理子过程backjump(index,I,M,ls,ito)操作接受部分赋值返回index,I,M,ls和目标索引ito,并返回部分分配的限制,直到并包括包含索引ito的级别。 该操作返回一个记录,其中包含字段newindex,它是ito和index之间的新赋值的索引,新的索引映射newI,它的(依赖)类型是包含期望值的单个集合,以及新的决策堆栈newls,它必须是原始堆栈ls的一个子集,其中索引大于ito的所有决策文字都已被删除。propagate操作propagate(index,I,ls,M,K,src)返回新的推断状态index 定义反复扫描 这些条款用于识别新的隐含字面意思或冲突条款。每次向M添加新的隐含文字时,都会重新扫描子句。隐式文字是通过扫描子句中的文字以确定除了一个文字之外是否所有文字都伪造的。回想一下,analyze操作在一个冲突子句上进行反向链接,以产生一个具有唯一级别最大字面量的冲突引理运算analyze(index,I,ls,M,K,src,kk)接受一个由index,I,M和src组成的部分赋值,以及一个被部分赋值证伪的冲突子句kk它返回一个空的连接子句,一个最大字面量在级别0分配的连接引理,或者一个具有唯一级别最大字面量的连接引理正如预期的那样,analyze被递归地定义为使用kk中最大字面量的源子句反复解析kk子句,直到前一句中列举的条件之一成立。很容易检查解决方案中涉及的子句是相容的,并且由此产生的解决方案子句被部分赋值所证伪analyze的终止是因为maxlit是kk中的最大字面量,它的否定是源子句K 'clauses中的最大字面量3.4DPLL搜索在我们定义主要的DPLL搜索过程之前,我们介绍在此定义中使用的另外两个操作。PVS prelude库中的参数化提升数据类型通过不相交的联合向给定类型T添加了一个底部元素。它用于表示搜索的结果N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)311select(index,(I:imap(index):atom= 0(LAMBDA a:I(a)=0)(LETrr=propagate(index,I,ls, M,K,src),newindex=rrnewI = rr在...提升[T:TYPE]:数据类型开始bottom:bottom?up(down:T):up?端部提升操作select挑选一个根据I未赋值的原子。它使用了希尔伯特主要的DPLL搜索过程也是递归定义的。 除了部分赋值之外,它还接受输入子句集Kin,这是为了指定目的而包含的,以及当前子句集K,它用在搜索期间通过分析学习的冲突子句扩展Kin。该过程的签名dpllr如下所示DPLLR(索引,(I:bimap(index)),(ls:lstack(index,I)),M,(K_in:clause_table),(K:(extends_ct(K_in),src:source(index,I,M,ls,K)):RECURSIVE lift[model]=.dpllr函数返回一个提升的模型。值bottom表示输入是不满意的,值up(对dpllr结果的解释将在下一节中进行说明。搜索的第一步是应用传播来获得具有newindex、newI、newmodel和newsrc的记录。如果传播出现冲突并且决策堆栈为空,则dpllr报告不满意。否则,如果决策堆栈不为空,则dpllr将analyze应用于constriction子句。如果analyze返回空子句或级别为0的子句,则dpllr报告不满足。12N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3i=0LETresult =backjump(newindex,newI,newmodel,ls,maxlevel)IN dpllr(结果结果结果结果是,newmodel WITH[(abs(newlit)):=(newlit>0)],K_in,K WITHnewsrc WITH[(abs(newlit)):=(IFrr(ls)然后底部其他(LETkk = analyze(newindex,newI,ls,newmodel,K,newsrc,IN(IF null?(kk)然后底部其他LET newlit = maxliteral(newindex,newI,kk),nextindex = maxindex(newindex,newI,delete(newlit,kk)),maxlevel = maxlevel(newindex,newI,ls,nextindex)在如果maxlevel(newindex,newI,ls,newI(abs(newlit)=零然后底部其他...ENDIFENDIF))ENDIF)否 则 , analyze 返 回 的 冲 突 子 句 具 有 唯 一 的 level-maximum 字 面 量 。 应 用Backjumping来缩减部分赋值,将连接子句添加到K,并将最大文字添加到这个以连接子句为源的缩减在剩下的情况下,当propagate没有返回一个conclusive时,我们选择一个未赋值的文字作为下一级搜索的决策文字ELSE(LET M1 = rrI1 = rr如果I1(a)>0,则a =select(newindex,I1)INTHEN UP(M1)ELSE设I2 = I1,其中[(a):= newindex +1] IN dpllr(newindex + 1,I2,cons(a,ls),M1,K_in,K,newsrc)ENDIF)ENDIF))MEASURE(expt(m+1,m+1)-dweight(index,I,ls))终 止 度 量 是 dweight ( index , I , ls ) 增 加 到 界 限 expt ( m+1 ,m+1),其中expt是自然数指数的取幂运算递归定义操作dweight(index,I,ls)来计算表达式|(m + 1)(m-i).| ∗ (m +1)(m−i).dpllr过程的终止是正确性论证的主要部分。正如非正式证明所示,可靠性和完整性并不像终止性那样具有挑战性。我们将在下一节中描述正确性证明中的证明义务。N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)313dweight_bounded:递归判断dweight(index,(I:imap(index)),(ls:lstack(index,I))HAS_TYPEup to(expt(m+1,m+1)-expt(m+1,m- length(ls)4证明的一些亮点我们现在简单概述在验证dpllr时更重要的证明责任。有许多关于部分赋值的适度引理,我们省略了操作maxindex和maxliteral后跳的定义产生了一些重要的证明义务。关于backjump的主要声明是,给定一个部分赋值,backjump操作会删除索引等于或超过决策堆栈中严格大于给定目标索引的原子,后跳这个引理需要一个大约50个交互作用的归纳证明在分析的定义中,有一个解决步骤,其中子句κ在一个给定的部分赋值中被证伪的是在它的最大字面量上被解析的,而赋值的源子句证伪了最大字面量。有两个证据与此步骤相关的义务。第一个是证明归结步骤是兼容的,第二个是证明结果子句的最大索引比原始子句的最大索引这两个证明都是重要的。在传播操作的定义中,有两个有趣的证明义务。一个用于确保源子句对应于新添加隐式字面量满足源子句表的类型约束,第二个检查递归调用的结果的类型是否与签名中的预期类型匹配。PVS中的递归判断是对递归定义的类型判断,它假设由判断给出的期望类型保持递归电话对于analyze的定义,使用递归判断来表明返回的子句是子句集K的结果。另一个引理证明了由analyze返回的constricct引理被当前赋值所证伪。由dweight给出的部分分配的权重用于构造dpllr过程的终止度量。有一些重要的引理与这个定义有关。首先,给出了dweight有界的递归判断,证明了dweight的值有界于(m+1)(m +1)。 这项索赔生成4个TCC,其中一个具有涉及近50个相互作用的证明然后使用一点复杂的算法来限制后跳步骤的dweight的减少。 这是一个非常精细的证明,需要大约100次交互,只有少数的子证明只是复制粘贴其他分支上的证明。另一个引理表明,通过将隐含的文字添加到部分赋值中而获得的权重,可以超过从backjumping中损失的dweight。这个证明需要大约30次交互。最后,我们表明,每当部分分配是扩展的,dweight增加。这个证明需要大约100次交互,但其中一些只是来自其他分支的证明的14N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3source_empty_lstack:LEMMAFORALLindex,(I:imap(index)),(K:clause_table),(src:source(index,I, M,null,K)):满足(N,K)含义(见a:I(a)> 0隐含N(a)= M(a))dweight_extends:LEMMAFORALL(index: below(m)),(I:bimap(index)),(newindex:below(m)),(newI:bimap(newindex)),(ls:lstack(index,I)):index = newindex AND bextendsI?(index,I,newindex)(newI)隐含dweight(index,I,ls)<= dweight(newindex,newI,ls)现在,我们已经准备好处理主dpllr过程的终止和正确性。dpllr的定义产生了25个TCC,其中15个被证明是平凡的。其余10个部队派遣国需要10至90次相互作用的证据。其中只有两个是终止TCC,对应于定义的两种递归情况。第一个终止TCC需要40次交互,第二个约50次交互。在证明了dpllr定义的类型正确性和终止性之后,我们剩下的任务是证明它是合理和完整的。关键引理断言,如果决策栈为空,则部分赋值中的所有文字都由子句表K中的子句隐含。这个证明是不平凡的,需要近60次交互。最后,我们将dpllr的可靠性和完备性表示为递归判断,该判断断言如果dpllr返回一个模型,则该模型满足输入子句。相反,如果它没有返回一个模型,那么输入子句是不满意的。注意,后一个条件不管给定的部分赋值M如何都成立,这是因为部分赋值上的不变条件确保M中的任何不可收缩的赋值都是K的结果,因此K在。递归判断索赔产生4个部队派遣国,其证明步骤从20到50不等。这些证明中只有一个是真正具有挑战性的,对应于analyze返回一个0级冲突子句递归判断dpllr(index,(I:bimap(index)),(ls:lstack(index,I)),M,(K_in:clause_table),(K:(extends_ct(K_in),src:source(index,I,M,ls,K))HAS_TYPE{LL:lift[model]|(IF上去?(LL)THEN满足(down(LL),K_in)否则(FORALL N:不满足(N,K_in))(ENDIF)该证明共涉及331个引理或证明义务。所有的证据可以重新检查在约275 CPU秒的2.16 GHz的英特尔酷睿2双核MacBook与1GB的RAM。N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3155讨论DPLL 搜 索 程 序 ( 定 义 为 dpllr ) 的 正 确 性 证 明 主 要 是 在 第 二 作 者 ( 当 时 是E'colePolytechnique的一名本科生)在SRI International实习两个月时完成的。第一作者是PVS的共同开发者,而第二作者熟悉函数式编程,但之前没有交互式证明检查的经验。两位作者在前两周间歇性地共同研究了dpllr的定义,并进行了一些初步的证明。第二提交人独自完成了诉讼程序的终止证明。这个证明揭示了定义中的大量中等严重的错误,包括在最初的定义体中缺少不变量,不第一位作者随后在大约四天的时间里重新做了终止证明,使用这里显示的度量,然后在几天内完成了可靠性和完整性的论证。从我们的演示中可以清楚地看到,我们利用了PVS语言的许多特性,如函数、记录、谓词子类型、依赖类型、递归数据库、参数理论和类型判断(包括递归判断)。PVS中的谓词子类型和依赖类型提供了高级别的安全性,因为作为高阶函数语言,良好类型的PVS程序是安全的。除了选择操作之外,我们的形式化是在PVS的一个可执行片段中,我们最近扩展了该片段,以包括这里用于子句表的动态数组。除了通常的类型安全,PVS执行将不会遇到非终止,数组边界冲突,被零除,缺少情况,或任何其他执行错误,只要我们假设无限的资源。PVS中的依赖类型不仅仅用于类型安全。用户利用依赖类型和证明义务生成来捕获大部分规范和结构证明并不罕见。例如,PVS中的一些有趣的终止示例利用了高阶依赖类型[18]。PVS有很多管理类型约束的特性。类型检查器不生成无关紧要的TCC,而是检查包含的TCC.它还自动应用类型判断来计算表达式的多个类型。证明检查器具有自动排出TCC的策略,并且决策过程利用表达式上的任何已知类型约束。即便如此,像我们在这个证明中那样大量使用依赖类型仍然存在一些重大挑战许多证明需要为特定表达式显式引入类型约束。生成的TCC通常过于具体,这限制了它们作为引理的重用。同一证明义务往往可以在一份证明中产生多次。当然,这些问题可以很容易地通过一点计划来克服。然而,由于我们使用PVS来探索形式空间并发现证明,因此我们实际上并没有检查预先计划的证明。类型判断,特别是递归判断,是非常强大的,因为它们产生的证明义务,对应的只是一个定义的相关情况。总之,PVS类型系统对于捕获16N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)3数据类型不变量,但我们需要确定使用类型约束的更好方法和更有效的推理机制。我们的大部分证明都致力于证明dpllr的终止性。这里的挑战在于证明部分赋值,它会增长和收缩,最终必须停止增长。证明的挑战性部分并不在这是一种不确定性,它表明排序本身是有界的,并且数据类型不变量是满足的。最近,Maric [10]使用Isabelle/HOL验证了一个SAT求解器,它与这里描述的非常相似他的验证需要大约一个人年的时间和一个30,000行的证明脚本。他的形式化还涵盖了使用双文字观察技术的有效单位传播。他对子句和子句数据库都使用了列表表示,而我们对子句数据库使用了数组表示我们能在证明中实现更好的自动化水平吗?显然,非正式论证和正式证明之间的距离是相当大的。这在很大程度上与非正式证明中缺少的细节有关,但我们确实发现了自动化不足的量化器实例化等领域。SMT求解器Yices [5]与PVS集成,Yices的语言与PVS非常相似。然而,我们倾向于不使用它在探索性的证明建设。这是因为我们必须仔细识别完成证明所需的定义和引理。一旦有一个完整的证明,定理和引理,可以利用Yices来实现更大的自动化,以构造对变化更鲁棒的证明。在不牺牲可读性的情况下,在交互式证明中利用自动SMT求解器的思想并不容易。然而,可以更好地利用排除与证明无关的公式的精确解释的可用性。对于改进的量化器实例,一阶或高阶证明搜索在某些情况下可能是有用的,但基于e图匹配的算法可能更有帮助[8]。我们还计划研究以SMT求解器为中心的声明式证明风格。我们发现PVS的目标导向证明风格非常有利于探索,但声明式证明风格将产生更强大和更易于理解的证明6结论我们已经描述了使用PVS对基于DPLL的搜索过程进行的命题满足性的机械验证这一过程对验证提出了有趣的挑战,并可用作各种自动化和半自动化工具的挑战它也是一个很好的例子,用于试验不同风格的形式化。我们的验证是构建可信/验证的参考内核的第一步,用于检查其他不可信验证器的结果DPLL SAT求解器的形式化和证明利用了几个特征的PVS。例如,类型判断和递归类型判断在将证明分解为可管理的证明义务方面发挥着重要作用,这些证明义务包括:N. 尚卡尔,M。Vaucher/Electronic Notes in Theoretical Computer Science 269(2011)317对个案的反应有较大的证明。虽然我们的证明代表了初步和探索性的尝试,但我们计划研究更好的形式化和更大的自动化的途径,并检查更有效和更有表现力的满意度程序的验证,包括SMT求解器。虽然令人鼓舞的是,一个相对未经训练的用户可以建立复杂的证明,只有少量的电子邮件,我们相信,有很大的改进空间引用[1] R. S. Boyer和J S.摩尔 计算逻辑。 Academic Press,New York,NY,1979.[2] R. S. Boyer和J.S.摩尔纯Lisp的图灵完备性的机械证明。当代数学,29:133[3] R.E.布莱恩特基于图的布尔函数操作算法。IEEE Transactions on Computers,C-35(8):677[4] E. M. Clarke,Orna Grumberg,and Doron Peled. 模型检查。 MIT Press,1999.[5] Bruno Dutertre和Leonardo de Barcelona。 Yices SMT求解器。 http://yices.csl.sri.com/,2006年。[6] M. Davis,G. Logemann和D.洛夫兰 一种用于定理证明的机器程序。 Communications of the ACM,5(7):394-397,July 1962.转载于Siekmann和Wrightson [19],第267-270
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功