没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记125(2005)103-116www.elsevier.com/locate/entcsIsabelle/HOL的边界模型生成Tjark Weber杰克·韦伯1,2在这一点上,Tec hnis heU iv ersita t t t Munc henBoltzmnstr. 3,D-85748Garc hingb. Mu�nchen,Germany摘要从高阶逻辑(在简单类型λ演算之上)到命题逻辑的转换提出,使得所得到的命题公式是令人满意的,如果HOL公式有 一个给定的有限大小的模型。然后可以使用标准SAT求解器来搜索满意的分配,并且可以将这样的分配转换回HOL公式的模型。该算法已在交互式定理证明器Isabelle/HOL中实现,用于自动生成非定理的反模型。保留字:高阶逻辑,有限模型生成,交互式定理证明1介绍交互式定理证明器已经增强了许多自动证明程序,用于不同的应用领域。然而,当自动证明尝试失败时,用户通常很少得到关于原因的信息。可能需要证明一个额外的引理,需要推广一个归纳假设,或者试图证明的公式无效。在这种情况下,一个可以反驳非定理的自动工具将是有用的。本文提出了一种从高阶逻辑到命题逻辑(无量化器布尔公式)的转换,使得命题公式是满意的当且仅当HOL公式具有给定有限大小的模型1这项工作得到了德国研究基金会计算机科学逻辑博士项目的支持2 电子邮件地址:webertj@in.tum.de1571-0661 © 2005由Elsevier B. V.出版,CC BY-NC-ND许可下开放获取。doi:10.1016/j.entcs.2004.10.027104T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103即涉及不超过给定数量的元件。然后可以使用标准SAT求解器来搜索满意的分配,如果找到这样的分配,则可以很容易地将其转换回HOL公式的模型。使用这种转换来生成HOL公式的(反)模型的算法已经在交互式定理证明器Is- abelle/HOL [15]中实现。该算法不是一个(半)决策过程:如果公式没有给定大小的模型,它可能仍然有更大或无限的模型。该算法的适用性也受到其复杂性的限制,这对于高阶逻辑来说是非初等的。然而,在实践中出现的公式通常具有小模型,并且与本文中描述的方法类似的方法的有用性已经在[10]中得到证实第2节介绍本文所考虑的逻辑的语法和语义,这是在简单类型λ演算之上的高阶逻辑的一个版本。模型生成算法,特别是翻译成propo- sitional逻辑在第3节中描述。最后,我们在第4节中做一些总结。2HOL逻辑我们的翻译可以处理HOL [9]和Isabelle/HOL定理证明器背后的大部分逻辑。这种逻辑最初是基于丘奇在这一节中,我们介绍了相关片段的语法和集合论语义。HOL逻辑的完整描述,包括证明系统,可以在[8]中找到。我们区分了类型和术语,它们分别用来表示某些集合和集合的元素。类型σ由以下文法给出,其中α的范围是类型变量的可数无限集TVσ::= 0 |α |σ → σ。类型变量代表任意非空集合。类型o表示一个可分辨的二元集合{T,n}。如果σ1和σ2是类型,则σ1→σ2是定义域为σ1值域为σ2的函数类型。它表示从定义域所表示的集合到值域所表示的集合的所有全函数的集合通常,→与右相关联,即σ1→σ2→σ3是σ1→(σ2→σ3)。我们假设一个可数无限集合V 的变量。 类型为tσσ是(显式类型的)变量、逻辑常数、应用程序或λ-T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103105J12122抽象 因此,术语由以下语法给出:tσ::= xσ|cσ|(tσJ→σ tσJ)σ|(λxσ1. tσ2)σ1 →σ2,其中xσ在变量范围内,cσ是=σo→o→o(蕴涵)或=σJ→σJ→o(σ上的等式),通常用fix表示。其他逻辑常数,包括λo→o→o、λo→o→o、<$o→o和任意阶的量化器,都可以定义为λ-项[1]。O型项称为公式。我们现在定义术语的语义。 设tσ是σ型项,tv(tσ)TV是所有在tσ中出现的类型变量的集合。 tv可以在一个辅助函数tvJ的帮助下归纳定义,该函数收集了类型中出现的类型变量:tvJ(o) =0,tvJ(α)={α},tvJ(σ1→σ2)=tvJ(σ1)<$tvJ(σ2),和tv(xσ)=tvJ(σ),tv(cσ)=tvJ(σ),J Jtv((tσJ→σtσJ)σ)=tv(tσJ→σ)tv(tσJ),tv((λxσ. tσ)σ →σ)= tvJ(σ1)tv(tσ)。注意,tv(tσ)不一定包含在tvJ(σ)中。 类型σ,tvJ(σ)/=σ而tv(tσ)≠ 0的项tσ称为多态的。此外,设fv(tσ)V是出现在中的所有自由变量的集合,tσ,通常定义为:fv(xσ)={xσ},fv(cσ) =σ,J Jfv((tσJ→σ tσJ)σ)=fv(tσJ→σ)<$fv(tσJ),fv((λxσ1. tσ2)σ1 →σ2)= fv(tσ2)\ {xσ1}。显然,tv(tσ)和fv(tσ)是有限的。tσ的环境D是一个函数,它为每个类型变量α∈tv(tσ)分配一个非空集合D(α)。类型的语义w.r.t.该环境由下式正式给出:[[o]]D={T,},[[α]]D=D(α),[[σ1→σ2]]D=[[σ2]]D[[σ1]]D。对tσw.r.t.环境D映射每个变量xσJ∈fv(tσ)到由类型σJ表示的集合的元素A(xσJ)。 给予106T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103JDD⎧DDDDD变量赋值A,变量xσJ∈V,以及由σ表示的集合的元素d,设A[xσJ<$→d]是将xσJ映射到d的赋值,并且v/=xσJ到A(v)。现在术语的语义w.r.t.环境D和赋值A由下式给出:[[xσ]]A=A(xσ),[[=o→o→o]]A是发送一⎧T,T到T⎪埃托·埃什特、⎪⊥,TtoT⎪阿托·T·阿托J[[=σJ→σJ→o]]D是发送x,y∈[[σ]]D的函数如果x=y,到、否则,JA AJA[[(tσJ→σtσJ)σ]]D=[[tσJ→σ]]D([[tσJ]]D)(函数应用),[[(λ xσ. tσ)σ→σ]]A是函数,它表示ea chd∈[[σ1]]1212 D至[tσ2D]]A[xσ1<$→d].因此,术语tσ的语义是由类型表示的集合的元素[A][a][b][a][a][b][a][b][3有界模型生成HOL公式φ=t0的模型生成分几个步骤进行。 我们首先通过为φ选择一个只包含有限集合的环境D来固定模型的大小。请注意,环境是由它们分配给类型变量的集合的大小唯一确定的,直到同构元素的名称无关紧要。对于每个由类型变量表示的集合,如果有一个固定的有限大小,那么每个类型都表示一个有限集合:|O|= 2和|=的|σ2|σ1||σ1|. 我们现在的任务是根据不同的情况[[φ]]A=T。 (To生成一个反模型,我们可以考虑<$φ,或者等价地=.) 在这个我们已经可以把有界模型生成看作是满足性检查,其中搜索树不一定是二进制的,但仍然是有限的。T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)1031073.1翻译成命题逻辑输入公式φ被转换成命题公式,当且仅当存在这样的变量赋值时,该命题公式才是可满足的。命题公式由以下文法给出:::=真假p ¬ ϕ ϕ ∨ ϕ ∧,|||||其中p的范围是布尔变量的可数无限集合。翻译是通过归纳的条款。虽然我们的目标是将一个o型项转换成一个命题公式,但需要一个更复杂的中间数据结构来转换子项(可能是任意类型的):我们使用树,其叶子被标记为命题公式。这些采油树的构造将在本节的其余部分中详细描述。一棵树的高度为1,宽度为m,对应的项的类型是类型变量(表示一个大小为m的集合)或o(对于m= 2),而一个n元函数或谓词由高度为n+ 1的树给出。我们将展示如何将应用和λ-抽象从术语级别“提升”到这个中间数据结构。为了更精确地定义平移,需要几个辅助函数。对于φ中的每个自由变量,create函数被调用一次,并返回一个树,树的叶子用布尔变量标记。(p)是新布尔变量的占位符,即,(p)的不同出现被不同的布尔变量替换。树的高度和宽度仅取决于φ中自由变量的类型。自由变量在φ中的多次出现被相同的树代替。create(o)= [(p),(p)],create(α)= [(p),.,(p)]的长度|α|、create(σ1→σ2) =[cre a te(σ2), . . ,create(σ2)]的长度|σ1|.从这些规则中可以看出,我们使用布尔变量是一元的,而不是二元的。这意味着我们需要n个变量来表示大小为n的类型的元素,而不是[log2n|变量然而,这些变量中的一个必须稍后设置为True(由于单位传播,这使得SAT求解器的搜索空间较小[21]),并且我们的编码允许相对简单的应用程序转换。为了确保布尔变量p1,..., pn被设置为True,一个命题公式wf [p1,.,nn]=.Σnpii=1n∧i,j=1i/=j(<$pi<$pj)108T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103KK对于e构造了一个形式为[p1, . . . . ,pn]t通过调用create(o)或create(α)来返回。 这个公式后来与翻译的结果结合在一起。TT和FF是分别对应于T和T的树TT =[True, False],FF=[False,True]。具有条目True和False的长度为n的第k个单位向量由uvn给出,同样地,UVn是具有条目TT和False的长度为n的第k个K KFF.⎧δn=Trueifn =k、否则为falseuv n= [δk,.,δk],k1nn=如果n=k,、否则,UV n= [k,.,J.K.]。k1n这些单位向量用于构建树,其叶子仅用命题常数(真/假)标记,表示特定(即第一,第二,.)正在考虑的领域的要素。还注意到TT = uv2,FF = uv2。1 2consts(σ)返回一个长度列表|σ|,包含一个表示树,用于everyyelemenntin[σ]]D. pick([x1, . . . ,xn])一个辅助函数,它返回一个列表,该列表包含每个列表xi中一个元素的所有可能选择。对于特殊情况,x1=... =xn,这对应于从n元集合到x1的元素的所有函数。consts(o)= [TT,FF],consts(α)= [uv |α|,...,uv |α|]、1|α|consts(σ1→ σ2)= pick([consts(σ2),. ,consts(σ2)])。“我的天,|σ 1|到目前为止所描述的功能足以定义不适用的术语的翻译。然而,应用程序的翻译需要更多的帮助函数。all返回命题公式列表的合取。map(f,l)将一元函数f应用于列表L.同样,treemap(f,t)将f应用于树t中的每个叶子。merge(g,t1,t2)通过将二元函数g应用于t1和t2中的对应叶来合并两棵树t1和t2。 两棵树必须具有相同的“结构”,即:迪塞尔.T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103109大多数人都在他们所包含的公式(但不是在他们的高度或宽度)。所有([101,.,n])= n1. 伊莱恩,m a p(f,[1, . . . . ,n])=[f(n1), . . , f(n)],treem a p(f,[1, . . ,n])=[f(n1), . . , f(n)],Treem a p(f,[t1, . . ,tn])=[treem a p(f,t1), . . ,treemap(f,tn)],merge g e(g,[1, . . ,[101],[102, . . . . ,2])=[g(1,2), . . ,g(α1,α2)],1n1n1 1n n合并器g e(g,[t1, . . . ,t1],[t2, . . . ,t2])=[merg e(g,t1,t2), . . ,merge(g,t1,t2)]。1n1n11Nnenum(t),对于表示[σ]] D的元素的树,计算一个比例矩阵[σ1, . . ,|σ|[X表示,trepesnttthef ir tt,. 、|[ σ ]] D的第-个元素。|-th element of [σ]] D.enum([1, . . ,n])=[n1, . . ,n],enum([t1,.,tn])= map(all,pick([enum(t1),.,enum(tn)])。函数由高度大于1的树表示。直观地说,当一个函数被应用于它的定义域的第 i 个 元 素 时 , 结 果 是 由 该 函 数 的 第 i 个 子 函 数 给 出 的 。 a pply ( t ,[101, . . ,n]),其中t是表示函数的树,并且如果函数参数等于函数定义域的第i个appl y([t1],[t1])=treema p((λ. (1),t1),appl y([t1,t2, . . ,tn],[n1,n2, . . ,n])=merg e((λJ. ϕ∨ϕJ),appl y([t1],[t1]),appl y([t2, . . ,tn],[n2, . . ,[n])。上面的λ是用来表示函数的元符号(与作为术语语法一部分的λ相对),而λ和λ是命题公式的构造函数我们现在准备好定义从项到命题公式树的平移TD通过将树的部分赋值B参数化到约束变量来参数化该平移。最初,这个部分赋值是空的,扩展每当翻译下降到一个λ-抽象的主体。翻译由以下规则给出110T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103DDDDDTB(xσ)=⎧<$B(xσ)如果xσ∈domB、否则创建(σ)TB(=0→0→0)=[[TT, FF],[TT, TT]],B|σJ||σJ|TD (= σJ→σJ→o)= [UV 1,...、紫外线|σJ|]、BJB BJTD((tσJ→σtσJ)σ)= apply(TD(tσJ→σ),enum(TD(tσJ),TB((λx.t))= [TB[xσ1→d1](t),.,TB[xσ1 →d|σ1|](t)],Dσ1σ2σ1→σ2Dσ2Dσ2当re[d1, . . . ,d|σ1|]=consts(σ1)。由于φ是一个类型为o的项,所以对于m u T(φ)T,T(φ)的S映射,平移的结果T(φ)必须是一个形式为[ T(φ)T,T(φ)]的树。D D D D命题3.1健全性、完整性。设f ∈{T,f},WF是在平移过程中构造的所有wf-公式的合取. 然后[[φ]]A=φ对于某个变量赋值A当且仅当WF<$T <$(φ)<$是满意。这个定理可以通过从公式推广到任意类型的项,然后在项上进行归纳来证明。我们省略细节。3.2找到满意的任务可使用现成的SAT求解器测试满足性。为此,已实现了DIMACS SAT和DIMACS CNF格式[6]的转换。转换成SAT格式是很简单的,而CNF格式(由zCha [14],BerkMin [7]和其他最先进的求解器支持)要求布尔公式为合取范式。我们将其转换为定义的CNF [19],以避免在此阶段出现指数爆破,并在必要时引入辅助布尔变量。更复杂的CNF转换可能会进一步增强我们方法的性能[11]。Isabelle/HOL运行在许多不同的平台上,安装应该尽可能简单。因此,我们还在Isabelle中实现了一个基于DPLL的朴素SAT求解器[5,21这个求解器并不意味着要取代外部求解器的严重应用,但它已被证明是足够有效的小例子。因此,它允许用户在不必担心安装一个额外的工具。如果SAT求解器无法找到满意的分配,则会在更大的环境中重复转换。用户可以指定几个终止条件:环境中集合的最大大小,要使用的布尔变量的数量限制,运行时限制。我们的顺序是T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103111DDDDDenumerate environments保证如果SAT求解器是完整的,则将找到最小w.r.t.其域的总大小。当然,对于不完整的(例如随机的)SAT求解器来说,这不一定是真的。3.3例证翻译考虑公式φ =((λxα. xα)α→α=(α→α)→(α→α)→oyα→α)o. 它唯一的类型变量是α,它唯一的自由变量是yα→α。在环境D中,|α| = 2(因此,|α→α| = 22= 4),φ的子项被转换成以下树:T((λ xα. xα)α→α)=[[True,False],[False,True]],T(=(α→α)→(α→α)→o) =[UV4,UV4,UV4,UV4],D1 2 3 4T(yα→α) =[[y0,y1],[y2,y3]]有四个布尔变量y0,y1,y2,y3另外还构造了两个wf-公式,即wf[y0,y1]=(y0y1)和wf [y2,y3]=(y2y3).应用该转换规则,我们得到(布尔公式等价于)和T(φ)T=y0y3T(φ)=(y0<$y2)<$(y1<$y2)<$(y1<$y3)。对于T_∞(φ)∈f [y0,y1]∈f [y2,y3],{y0<$→ True,y1<$→ False,y2<$→ True,y3<$→ False}。 假设[α]] D={a0,a1},这个赋值对应于将yα→α解释为将a0和a1都映射到a0的函数。3.4一些扩展:集合、希尔伯特第2节中描述的逻辑的几个扩展可以直接集成到我们的框架中。具有来自σ的元素的集合的类型σ集合同构于σ→o。集合隶属度x∈P成为谓词应用Px,集合理解{x。P可以简单地翻译为P。希尔伯特σ,满足公理φ:(φx. P x)=P(P)。112T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103JJJ同样,也是(σ→o)→σ型常数,满足φ:(x。x = a)= a,而arbitrary是一个完全未指定的多态常数。为了我们的翻译TD的目的,我们可以把这些逻辑常数当作自由变量,并引入布尔变量来确定它们的解释。对于φ和The,然后我们将原始公式φ与相关公理的合取(即分别为φφ或φTheφφ,或φφTheφφ如果和The都出现在φ中)。φ(或φThe)中的类型变量被实例化以匹配φ中的(或The)的类型。Isabelle/HOL允许归纳数据集的定义[2]。一般来说,具有自由构造函数的归纳数据库需要一个无限模型。我们通过只考虑有限片段来处理这些数据集(例如,直到上限的自然数,或直到一定长度的列表)。归纳数据集的翻译的详细描述将在别处给出。我们注意到,如果归纳数据类型只在输入公式中出现,那么为片段找到的模型总是可以扩展为完整数据类型的无限模型。然而,许多重要的数据库是非递归的,对于这些,情况更简单。例子有类型σ选项,它通过一个新元素增加一个给定的类型σ,乘积类型σ1×σ2,和和类型σ1+σ2。非递归数据类型定义的一般语法如下:(α1,.,αn)σ::= C1σ1...σ1| ... | Ck σk...σk,1m11mk其中Ci是数据类型详细说明其论点类型,所有σi仅引用先前定义的类型和类型变量从α1, . . . ,αn. 在有限的模型中,可以对数据类型进行解释;它的大小等于S:=Ki=1mij=1 |.|. 因此, 这种数据类型的 元 素 可以是由高1、宽S的树表示,数据类型构造函数Ci是一个σi→. → σi→(α1,. ,αn)σ,可用树表示1百万i高度为mi+1。3.5一些优化我们简要地描述了一些优化的翻译TD的实现。它们都不是算法的可靠性或完整性.在翻译过程中构造的布尔公式在代数上被简化,使用基本的代数定律,即,封闭的HOL公式简单地变成True或False。SAT求解器仅用于搜索自由变量的解释。T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103113大小为1的类型的变量可以用[True]表示,根本不使用布尔变量(而不是一个布尔变量x和wf[x]-公式x)。虽然由于单位传播,这在SAT求解器级别上几乎没有影响,但它允许对构造的布尔公式进行更广泛的简化。类似地,大小为2的类型的变量,包括类型为o的变量,可以由形式为[x,<$x]的树表示,而不是由tree[x0,x1]anda wf [x0,x1]-for mul a(x0x1).更重要的是,我们避免展开逻辑常数的定义(即, Tru eo,F a lseo,<$o→o,o→o→o,o→o→o,(σ→o)→o,(σ→o)→o)asλ-t erms尽可能. 相反,这些常量直接被它们的计数器替换命题逻辑中的部分。因为每一种类型都是有限的,所以任意阶的量化器都可以用有限合取或析取来代替。后者导致更一般的优化技术,也适用于其他函数和谓词(包括例如相等):即,将函数应用的规则特殊化到特定函数。而任何给定的函数都可以用树来表示,假设这些参数已经以树的形式给出,那么在参数上实现特定函数的操作通常比使用一般的转换规则更有效并将其应用于表示函数的树。对于= σ→σ→o,这避免了创建一个 树,其 中 ,|σ|2,而不是使用一个函数,该函数对表示[ σ ]] D的元素的树进行操作,它们的大小与|σ|(或可能记录|σ|)。3.6示例表1显示了我们的算法可以自动找到反模型的公式的一些示例。类型注释被抑制,反模型中的函数由它们的图形给出 表示唯一存在,定义为通常:快!X. P xx。P x(y. P y = Py = x)。反模型相当小,都是在几毫秒内发现的。这些例子的主要目的是说明底层逻辑的表达能力。4结论和未来工作我们提出了一个从高阶逻辑到命题公式的转换,使得所得到的命题公式是满意的当且仅当HOL公式具有给定有限大小的模型一个工作实现114T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103性质/配方反模型”Every function that is onto is“(不好意思。 你好f x = y)= f(x =y)你好g(f x)= x)D(α)={a0,a1},D(β)={b0}f={(a0,b0),(a1,b0)}”There exists a unique choice“(注:很好P x y)=(!F. 你好P x(fx))D(α)={a0},D(β)={b0,b1}P={(a0,{(b0,True),(b1,True)})}”The transitive closure ofA和B“D(α)={a0,a1}A={(a0,a1),(a1,a0),(a1,a1)}B={(a0,a0),(a1,a0),(a1,a1)}表1示例这个翻译,由大约2,800行用Standard ML [13]编写的代码组成,可以在Isabelle/HOL定理证明器中找到。可以使用标准SAT求解器来搜索对提议公式的满意分配,并且如果找到这样的分配,则可以将其转换为HOL公式的模型。这允许Isabelle/HOL中的非定理的有限反模型的自动生成。类似的翻译在[10]之前已经讨论过;本文的主要贡献是将其扩展到高阶逻辑以及与流行的交互式定理证明器的无缝集成。到目前为止,我们只将该技术应用于相对较小的示例。该算法的适用性受到其非初等复杂性的限制。我们相信,该算法仍然可以用于实际目的,因为许多公式具有小的模型。为了证实这一说法,并进一步评估我们方法的性能,我们计划进行一些更大的案例研究,可能来自加密协议验证领域[16,17]。我们还计划进一步优化[4,18],并将翻译扩展到其他Isabelle/HOL结构:最值得注意的是HOL的完整语言,包括类型运算符[8],但也包括公理类型类[20],归纳定义集和递归函数。在性能和可行性方面,一种值得评估的正交方法是使用外部(一阶)模型生成器。从HOL到一阶逻辑的必要转换可以基于Meng和Paulson最近的工作[12]。确认作者要感谢Martin Strecker,Tobias Nipkow和匿名裁判的宝贵意见。T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103115引用[1] Peter B.安德鲁斯数学逻辑和类型理论导论:通过证明求真,应用逻辑系列第27卷。KluwerAcademic Publishers,第二版,2002年7月。[2] 斯特凡·伯格韦尔和马库斯·温泽尔。HOL中的归纳数据库-形式逻辑中的经验教训。 在纽约。 别这样,G。 Dowek,A. 他的名字叫C。 宝莲寺,和L。Thery,编辑,高阶逻辑中的定理证明,第12届国际会议,TPHOLsSpringer,1999年。[3] 阿朗佐·丘奇简单类型论的一个公式。Journal of Symbolic Logic,5:56[4] KoenClaessenandndNikla s Sr ensson.新的技术要求改进MACE-结构化的模型查找。在CADE-19,车间W 4,模型计算[5] M. 戴维斯,G。 Logemann和D.洛夫兰一种用于定理证明的机器程序。Communications of the ACM,5:394[6] DIMACS满意度建议格式,一九九三年可 查 阅 ftp ://dimacs.rutgers.edu/pub/challenge/satisfiability/doc。[7] E. Goldberg和Y.诺维科夫BerkMin:一个快速而强大的SAT求解器。在欧洲设计自动化和测试(日期),第142-149页[8] M. J. C. Gordon和T. F.梅勒姆编辑们介绍HOL:高阶逻辑的定理证明环境。剑桥大学出版社,1993年。[9] M. J. C. Gordon和A. M.皮茨逻辑与系统在J. Bowen,编辑,Towards Verified Systems,Real-Time Safety Critical Systems Series第2卷,第49爱思唯尔,1994年。[10] 丹尼尔·杰克逊。自动化一阶关系逻辑。在Proc. ACM SIGSOFT Conf. Foundations of SoftwareEngineering,第130-139页[11] 保罗·杰克逊和丹尼尔·谢里登快速CNF转换的最优性及其与SAT的使用。技术报告APES-82-2004,APES研究小组,2004年3月。[12] Jia Meng和Lawrence C.保尔森使用解析支持交互式证明的实验。在David Basin和MichaelRusinowitch,编辑,自动推理Springer,2004.[13] 罗宾·米尔纳,麦兹·托夫特,罗伯特·哈珀,大卫·麦奎因。标准ML的定义-修订版。MIT Press,May 1997.[14] M.莫斯凯维奇角Madigan,Y.赵湖,加-地Zhang和S.马利克 Cha Cha:Engineering an efficientSAT solver. 在proc 第38届设计自动化会议,拉斯维加斯,2001年6月。[15] 放大图片作者:Tobias Nipkow,Lawrence C.保尔森和马库斯·温泽尔。Isabelle/HOL -施普林格,2002年。[16] 劳伦斯角,澳-地保尔森 验证密码协议的归纳方法。 计算机安全杂志,6:85[17] 格雷厄姆·斯蒂尔,艾伦·邦迪,还有埃文·丹尼.寻找归纳推理的反例并发现安全协议攻击。AISBJournal,1(2),2002.[18] 塔内尔·塔梅特有限模型的建立:改进和比较。 在CADE-19,车间W 4,模型计算[19] G. 蔡廷 论命题演算中推导的复杂性。 以. Slisenko,编辑,研究在建设性数学和数理逻辑,第2,第115116T. Weber/Electronic Notes in Theoretical Computer Science 125(2005)103[20] 马库斯·温泽尔高阶逻辑中的类型类和重载。 在艾尔莎湖 Gunter和Amy P.1997年TPHOLs第10届国际会议,《高阶逻辑中的定理证明》Springer,1997年。[21] L. Zhang和S.马利克寻找有效的布尔可满足性求解器。 在Andrei Voronkov,编辑,Proceedingsof the 8th International Conference on Computer Aided Deduction (CADE 2002),卷2392计算机科学讲义。施普林格,2002年。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功