没有合适的资源?快使用搜索试试~ 我知道了~
证明规划系统的比较与分析
理论计算机科学电子笔记151(2006)93-110www.elsevier.com/locate/entcs验证规划系统的比较:λCLAM、Kemega和IsaPlanner路易丝·A丹尼斯1,2英国诺丁汉大学计算机科学与信息技术学院Mateja Jamnik1,3剑桥大学计算机实验室剑桥大学,英国Martin Pollet马丁·波利特1,4Fachbereich信息UiversitüatdesSaarlandndess,Saarbruücken,Germanny摘要我们提出了一个框架来描述证明规划。这个框架是基于一个decomposition的证明规划器到规划状态,证明语言,证明计划,证明方法,证明修订、校对控制和规划算法。一我们使用这个框架来激励比较最近的三个证明规划系统,λ CLM,LASMEGA和I SA P LANNER,并演示了该框架如何使我们能够以一致的方式讨论和说明它们的相似性和差异性。这一分析表明,证据控制和使用的上下文信息在规划国家的关键领域需要进一步调查。保留字: 证明计划1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.11.02594洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)931引言证明计划是由Alan Bundy [1]引入的,作为证明自动化的新范式。而不是使用低层次的逻辑推理规则,证明结构是自动化的,使用所谓的证明方法,捕捉常见的推理模式。证明计划者搜索定理的证明计划。 然后可以执行该计划,以根据底层逻辑推理规则导出完全形式化的证明。搜索空间往往小于推理规则[3,8]的水平。这是由于在计划中出现的证明方法的更抽象的性质,特别是,搜索空间的结构,这是可能的,通过这种抽象。因此,校对计划的重点是提供组织应用这些校对步骤的机制证据规划的一个显著特征是,它生成的证据中的推理模式是透明的,失败可以修补。最近的案例研究表明,证明规划为计算系统的集成提供了基础,用于指导自动证明构建和执行证明步骤[7,4]。例如,计算机代数系统可用于在证明步骤中实例化变量,约束求解器可用于收集和管理不等式,理论形成系统可用于构造代数结构的鉴别性质。这些案例研究表明,证明规划是一个合适的框架集成到演绎系统的计算算法,但现代分析的证明规划方法(特别是,参考故障恢复)仍然缺失。我们认为现在是巩固这些想法的时候了这一领域的进步和最新技术。因此,本文的目的是(在§ 2中)提出证明规划的各个特征的明确抽象定义,以便为讨论和比较证明规划系统提供一个共同的框架。我们通过(在§3中)比较三个最近的证明规划系 统 来 说 明 我 们 的 框 架 的 使 用 : λCLA M , λ CLMEGA 和 ISAPLANNER。1这项工作得到了EPSRC赠款GR/N37314/01和GR/S 01771/01、EP-SRC高级研究奖学金GR/R76783、SFB 378项目赠款和欧洲委员会IHP Calculemus项目赠款HPRN-CT-2000-00102的支持。感谢Lucas Dixon为本文的早期版本所做的工作,以及Ewen McLean富有成效的讨论。2 电子邮件地址:lad@cs.nott.ac.uk3电子邮件:Mateja. cl.cam.ac.uk4 电子邮件地址:pollet@ags.uni-sb.de洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93952验证规划正如这个词所描述的那样,证明规划在概念上与人工智能(AI)中的传统规划有关。在传统的人工智能规划中,描述一个问题是由关于初始状态和目标状态的逻辑句子组成的。目标状态由一个逻辑查询语句描述,该语句询问如何从初始状态实现某些情况。 一个证明问题可以被看作是一个规划问题,当我们确定问题的局部假设和理论,其中问题被制定为初始状态。证明问题的结论对应于目标状态。规划算子描述了规划状态到新状态的转换规划算子通常由其前提条件和结果表示。前提条件指定了在规划状态下需要为真的操作操作符的效果指定如何在应用了操作符之后,情况发生了变化。证明规划中的证明方法的使用就是源于这种范式。(证明)规划器搜索一个操作符序列,通过该操作符序列可以将初始状态转换为目标状态。一个成功的过程的操作者的顺序是一个计划。 由于不需要线性化方法,证明计划是树或DAG(有向无环图)。证明计划类似于人工智能计划,因为它表示如何解决(证明)规划问题(定理)的描述,而不是表示计划的执行(形式证明)。与人工智能规划一样,规划过程的结构化使用搜索算法和控制知识来决定在选择点采取哪条路径在打样计划中,许多术语的使用变得有些超载和混乱.在可能的情况下,我们力求保留常用术语,但我们将努力使我们的用法准确。 值得注意的是,我们框架中使用的术语是基于功能而不是命名的。有可能一些同名的特征可能出现在我们的框架针对每个系统不同地分类的两个证明规划系统中(例如,λCLA M的复合方法只能松散地放在我们框架的证明方法类别中我们认为这这是一种优势,因为它使差异更容易被感知,即使术语是混乱的。我们的框架基于对组件的分类,其中大部分组件可用于所有证明规划系统。96洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)932.1校对计划状态大多数关于证明计划的文献将证明计划者描述为部分证明计划。然而,Dixon和Fleuriot [5]的一个重要见解是注意到证明规划器对证明规划状态进行操作。我们考虑国家的所有组成部分,也就是说,所有的信息来源以及所有可以被校对计划操纵的部分这些是:证明目标:需要证明或解决的目标。证明计划:在某种抽象级别上的证明(可以是部分的)。历史:证据搜索过程的记录,包括回溯步骤和失败的操作员。控制信息:用于选择下一个打样计划操作员。上下文:存储额外信息的存储库。这些信息可以附加到条款、验证计划中,或者以控制状态的形式为什么一个目标是不可解决的)。规划状态中最不明确的部分是背景。这在我们考虑的所有系统中都是不同的。上下文对于搜索问题的证明是有用的,但是对于从证明计划重构形式证明是不必要的。在校样规划期间,如在AI规划中,校样规划状态由校样规划操作符转换。可以根据操作符可以访问和操作的规划状态的哪些位来导出许多类别的操作符。然而,在实践中,规划算子在验证规划中的使用分为不同的常见类别:证明方法描述了如何将目标转换为新的子目标;它们也可以使用和操作来自上下文的信息。证明修订描述了对失败的反应。 它们是关于目标、证明计划、控制知识和背景信息的全局操作。其他类别的操作员与以下机制有关校对控制用于选择下一个目标和下一个校对计划操作员。验证控制可以使用验证控制操作符来操纵控制知识,然后分析控制知识(可能与验证计划、历史和上下文一起)以选择下一个操作符。证明扩展是将证明计划转换为形式证明。在下文中,我们将更详细地描述这些操作符和机制证明扩展被认为是在层次结构的上下文中证明计划和用于形式证明的语言洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93972.2证明语言证明语言(对象语言)是逻辑演算的公式和推理规则的语言,在逻辑演算中进行证明计划尝试。对象级别的证明通常是证明计划过程的最终结果,这个对象级别的证明是从证明计划中生成的系统在对象语言的表达能力上有所不同,例如,一些对象语言排除了元变量(在搜索存在性量化变量的见证2.3证明计划术语证明计划最初用于描述搜索空间的显式结构和证明本身的高级表示在后面的描述中,该术语通常用于描述后者。因此,我们采用这种含义:证明计划描述了证明计划的结果。我们将使用术语证明控制来描述搜索空间结构。证明计划是存储证明方法应用于目标的结果的图,并且是将抽象证明扩展为微积分级别证明的基础。对证明方法的引用被存储,并且可以被视为节点的正当性。因此,一个证明计划可以被解释为一个抽象的证明,或者更确切地说,一个问题的证明草图。证明计划可能包含不同的,可能是许多抽象级别证明方法的扩展导致更详细的证明计划,形式证明处于最低级别。形式证明的构建可以与证明规划步骤交织在一起,或者作为证明搜索之后的验证阶段来实现。有多种技术可以将证明计划扩展为更具体的计划。目前,所有系统中的每个证明方法都在局部这意味着证明计划的结构是由逻辑演算决定的(见3.2节)。抽象是通过用于证明控制的机制来实现的。证明方法的序列可以被压缩为单个步骤,该步骤被标记为负责选择该方法序列的证明控制2.4证明方法证明方法描述了如何将一个目标转换为新的子目标,并为这种操作提供了一个合理的解释它无法获得当前验证计划或历史中保存的信息,也不知道其他方法。只有特定的目标和与该目标相关的上下文信息才可用于该方法。98洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93在文献中,我们发现证明方法通常被定义为策略的声明性描述,其中策略是可以应用于目标以生成子目标并保证推导正确性的函数。方法的声明性质不一定事先提供有关该方法所执行的操作的任何信息其应用(见§3.4.1)。在这方面,一种策略性和声明性的方法包含相同程度的信息,唯一的区别是声明性方法需要解释器来实际执行操作。显然,在某种程度上,证明方法会影响计划状态的变化,特别是部分证明计划。证明方法和证明规划算子之间的关系因系统而异战术和方法之间的差异是许多争论的根源。我们的框架允许我们观察到,一个战术不能访问任何上下文信息,所以战术形成一个子集的方法。每一种只作用于用公式的证明语言表达的目标的方法(即,在G到prooducesubgoalsS<$)可以通过一个类似于活动的方法进行模拟,这是本应用程序的附加子目标(即,例如, SG)。Soamethodd在抽象问题上区分解决问题所需的子目标。级别和子目标(在某些系统中是隐式的)。因此,方法相对于策略的主要区别特征是方法可以访问并能够操作上下文信息,而LCF风格的策略仅操作对象级别的公式。作为第二个特征,方法通常保留一些隐含的子目标,或者至少单独分类,以表明它们将通过扩展来解决,而策略使所有子目标明确,并赋予它们相同的地位。2.5校样修订校样修订是校样规划中最强大的机制。校样修订在所有系统中都会因失败而触发。失败通常意味着一个目标不能被关闭,要么是因为没有适用的证明方法,要么是计划者循环。然而,可以将失败更一般地解释为确定需要对方法进行某种重大改变的任何过程。对失败的标准反应是回溯:验证计划操作符,其从验证计划中删除节点并适当地更新控制信息以防止该分支被重新探索。证明计划的抽象性质允许对故障进行非常复杂的分析。分析是基于证明方法,或证明计划和历史。如何反应的规范包括关于从何处重新开始(验证计划的操作)和如何继续(验证控制信息的操作)的信息。洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93992.6证明控制验证控制使用规划状态中的控制信息来确定下一个目标和验证规划算子的选择在当前系统中,检验控制信息或者以分析当前检验计划和历史的控制规则的这个描述是操纵的证明规划的进展和实际的运营商应用。更新后的描述称为延续。 在某些情况下,延续本身被视为证明计划操作符。因此,在各种系统中,验证控制由计划状态中的控制信息和修改该信息的验证计划操作符的混合来指示重要的是要考虑控制操作符,控制信息,以及使用信息来选择下一个操作符的机制,以便理解如何控制证明搜索。因此,在我们的框架中,我们将所有这些都放在证明控制的标题下,而不是单独作为规划状态,规划算子和规划算法的一部分。2.7规划算法证明规划系统的最后一个组成部分是规划算法。规划算法负责搜索解决给定问题的证明计划。它必须处理控制信息,应用验证方法,更新验证计划,并切换到验证修订。3三种打样规划系统的比较我们现在通过使用它来比较证明规划器来说明我们的框架。本节末尾的表1总结了这些系统之间的主要特征以及它们与我们的框架之间的关系验证计划在多个系统中实施。第一个证明计划者,CLA M [1]是为了用数学归纳法证明定理而设计的。其后继者λCLA M [11]已被推广到高阶逻辑。另一个众所周知的系统是大型证明计划器[9]。在IBM中,证明规划被视为面向人类的推理技术的传统,用于数学定理证明(而不是面向逻辑的技术,如决议)。CUMMEGA集成了各种其他数学服务,如传统的自动定理证明器,知识库,计算机代数系统等。最后,ISA PLANNER系统[5]是交互式的证明规划器。100洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93定理证明者ISABELLE[10]. ISA PLANNER交织证明规划与证明计划我们使用这三个证明规划系统的比较作为案例研究,以说明我们的框架从§2可以作为讨论证明规划系统的建设的基础。3.1证明规划状态在ISA规划器中,规划状态是由证明计划、证明上下文和延续形式的控制信息目标被隐式地表示为证明计划的开放节点证明上下文可能包含-获取任意信息。伊萨·普兰纳可以接触到伊莎贝尔,包括理论库和重写规则的信息将用于简化。证明规划算子是关于规划状态的函数,称为推理技术。λCLA MM使用的上下文信息λCL包括附加到术语的注释和多个全局列表(例如用于重写的定理规划状态包含目标,证明计划,控制规则,一个或多个约束存储作为上下文,以及证明搜索的历史。目标可以是证明目标,也就是说,要证明的公式,或变量的实例化目标。约束存储用于收集instan- tiation目标的信息。存在用于不同域的附加约束存储。历史有三个部分:证明计划被视为成功方法应用的历史,回溯步骤的历史和战略历史。历史是一个必不可少的一部分,阿斯塔纳的证明规划状态。它被证明控制使用,我们将在§ 3.6中深入讨论。OMEGA还使用附加到术语和目标的注释。我们对证据规划者的分析表明,规划运营商使用的一些信息并没有明确提到规划状态的一部分。例如,λCLA M中的全局列表,其中存储定理,其由用于重写的证明方法使用。类似类型的参数也存在于MySQL中,但它们是在MYSQL理想情况下,这些信息应该作为规划状态上下文的一部分明确表示,这将允许与它们进行推理,例如,用修改后的定理列表开始新的规划尝试由于不同的系统使用不同种类的上下文信息,并且由于这些信息也依赖于证明域,因此我们提出了证明上下文的概念作为信息的可扩展存储库。在交互式定理证明器中,洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93101是由人类用户提供的,在证明计划中,必须在系统内对该信息进行建模和表示。背景的概念可能会导致复杂化。由于存在许多不同类型的上下文信息,操作员可能必须意识到这些区别。依赖于不同类型的上下文信息并作用于不同类型的上下文信息的混合运算符可能导致证明计划和上下文之间的不一致。显然,需要进一步分析和理解证据背景在证据规划中的作用。3.2证明语言OMEGA使用类型化的λ-演算来计算公式。基本演算是根岑自然演绎演算(ND)的高阶版本λCLA MλCLA M然而,λCLA M没有采用明确的对象级推理规则。因此,它的目标语言是一个语法实体,具有作为高阶微积分的松散解释LEMEGA和λCLA M将存在量化变量产生的自由变量视为元变量,而元变量不是证明语言的一部分ISA PLANNER使用ISABELLE这意味着它可以访问在对象级别实现元变量的丰富语言3.3证明计划所有三个校样规划系统都将校样规划表示为DAG。的情况下对于ISA PLANNER和λCLA M,该表示被限制为树。的这些DAG的节点用目标公式和假设标记。在所有系统中,节点都包含一些对证明操作的引用,这些操作负责创建节点,可以解释为节点的抽象证明。显然,IBMMEGA证明计划比λCLA M和ISA PLANNER使用的树。DAG在超大型允许节点被重用,以实现多个目标。证明计划可以在不同的抽象层次上表达。通过扩展实现了向更详细的打样图的转换。扩展用于生成可验证的形式证明。在Proof Search之后的第二阶段,对Proof Plan进行验证:所有的元变量都被替换为它们的见证项,每个证明方法都被扩展为可能包含其他方法的子证明。当所有的证明步骤都是微积分级别的规则时,过程停止,以便可以检查完全扩展的证明102洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93由λCLA M产生的证明计划通过其相应的证明方法的名称来证明各个证明步骤。在λCLA M中,没有可用的证明计划的实际扩展。然而,一种类似于预计将扩大到马达加斯加每个证明方法都与一个策略相关联(对于LCF风格的定理证明器),因此证明计划可以被视为一个可以执行的策略树在伊萨P兰纳扩展是交错的应用证明方法.一种方法只有在可以构造出该方法所执行的操作的形式证明时才适用。证明计划表示为证明脚本中的ISAR语言。在不同系统的比较中,出现了一个明确的设计选择,即验证是否与施工过程交织在推迟扩展阶段可以允许证明搜索使用有效的算法方法来计算子目标,并将正式证明的实际它还允许独立于任何对象语言特性生成证明计划。另一方面,交错扩展允许系统在适当的情况下使用存在于底层系统中的策略。在两个阶段(即,延期)扩展扩展中的失败通常导致整个证明计划的修订,而对于交叉验证,这种不正确的证明计划在证明搜索期间被排除交错执行等效于两阶段方法,其中可以将交错执行中的目标标记为扩展目标。证明计划背后的最初想法是构建一个Meta级别的证明计划,然后再重建底层的形式证明。这是基于对数学实践的观察,在那里很少需要担心在“纸笔”证明中使用精确的逻辑,但是如果必要的话方法的局部扩展意味着形式证明比证明计划更详细,同时仍然保持相同的结构。形式证明和证明计划之间的这种紧密联系,促进了证明算子的实现。一些逻辑对抽象证明计划构造的约束比其他逻辑更多。例如,ND对采取证明步骤的顺序非常敏感,这决定了一些证明操作符的实现方式。然而,从“纸笔”的证明计划也可以通过折叠步骤序列来抽象。它主要用于接口。它允许用户洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)931033.4证明方法我们在这里使用证明方法这个术语来描述如何将一个目标转换成一个(可能是空的)子目标列表,以及如何操作上下文。这些方法在λCLA M中称为原子方法,在墨西哥城。它们在ISA PLANNER中没有被明确识别,但它们是该系统中可用的推理技术λCLA M和λ CLMEGA包含输入、输出、参数和前提条件槽的真值。输入和输出槽用于匹配和生成目标。这个框架结构为用户提供了一个接口来创建他们自己的方法,无论是我们-使用λCLA M中的任意λPROLOG代码,或专用解释语言为这一任务而开发的。ISA PLANNER使用一种单一的可扩展语言来编码技术,这些技术是规划状态的功能。有可能将这些技术的一个子集识别为证明方法,因为它们的主要功能是产生新的子目标。它们中的一些甚至包含类似于证明上下文中的方法先决条件的声明性信息。此声明性信息用于启用校样修订。在Λ CL和λCLA M中,证明方法的(半)声明性结构允许它们被视为证明步骤的描述,系统子系统应用该证明步骤来创建证明规划算子。系统自动化-及时更新验证计划和历史记录等。我说普兰纳推理状态是证明规划状态的显式函数。尽管我们将其中一些方法确定为方法,但这些方法是用新的目标节点扩展部分证明计划的方法同样值得注意的是,ISAPLANNER在大多数出版物的证明规划,参数被忽略的方法的描述。我们明确提到参数作为用于方法的帧数据结构中的槽,因为这允许从证明控制层到证明方法的信息流。参数可以在验证控件选择方法3.4.1说明性在不同的方法编码形式中,OMEGA用于输入和输出的语言是固定的,存在用于前提条件的解释语言,并且扩展由包含子证明的声明性规范的证明模式人们曾设想,前置条件的语言将达到一个固定点,但事实证明,新的领域需要新类型的前置条件。104洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93选项。在λCLA M中,前置条件直接用编程语言表示。相比之下,ISAPLANNER中的槽的声明不是固定的,并且声明性仅通过在证明上下文中可选地包含“类前置条件”语句来提供因此,我们不能在任何系统中谈论证明方法的完全声明性语言。采用声明式语言有三个主要动机:操作符的分析;为希望创建自己的证明规划操作符的系统用户简化实现;以及确定如何引入(和删除)步骤。在实践中,这些理由中的第一个对于证明计划没有多大用处。证明规划系统中的许多方法无法分析。例如,考虑一种应用计算机代数算法对目标进行简化的方法。要知道这种方法的效果,唯一的方法是将它应用于一个具体的目标。用户通常只需要简单的工具来对公式进行语法操作,这些工具可以使用输入模式提供。更复杂的方法似乎需要一种完全灵活的编程语言来编写专家用户需要掌握的任意复杂的先决条件。声明性语言介于这两种复杂程度之间的理由似乎很薄弱。因此,使用陈述性前提的理由只有一个,那就是在分析扩展步骤或失败推理时使用它们。再一次,似乎只有输入和输出方案在这里是真正必要的,因为其他信息可以重新构造(见3.5节)。3.5校样修订λCLA M有明确的证明批评者[6],他们习惯于用撕裂[2]获得巨大的效果。传统上,当一种方法不适用时,就会引发批评,但也可能是主动引发的,并且倾向于使用对方法前提条件的分析来激励对证明计划的修改。 与只添加新目标的方法相反,批评者通常会删除或替换结我萨普兰纳大规模操纵验证计划它们在证明上下文中使用方法存储的声明性信息,而不是显式的前提条件分析。本质上,批评者被用来跳过搜索空间的分支,否则将被费力地探索(通常是通过回溯),并将新的领域引入搜索空间。在大规模验证中,有两种可能的不成功退出证明规划策略的类型。要 么 没有适用的方法(称为失败),要么证明规划策略本身可能导致中断。在策略层的故障分析被称为Meta推理。Meta推理是基于洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93105基于对当前目标、局部论证方案和历史的分析,而不是基于方法所有系统都允许检测故障,这些故障与一种方法没有直接联系,例如,证明搜索中的循环一个批评家分析一个给定方法的前提条件是有局限性的。由于前提条件的语言不是完全声明性的,批评者取决于前提条件是如何表达的。因此,引入一个批评家可能会使证明方法有必要改变,而证明方法的改变会对相应的批评家产生影响。当批评者对证明计划状态执行其自己的分析时,或者该方法在证明上下文中存储关于失败的附加信息时,可以避免批评者和证明方法之间的修订通常由几个不同的部分组成,例如,回溯,改变校样控制,继续特定的目标。在IBM中,这些步骤被实现为不同的策略,但是(策略)控制规则只能选择紧接着的下一个策略。这意味着,不可能表达这些步骤的确切组合。 在每一步之后,都需要分析下一步应该做什么。为此,有必要区分针对不同修订版本执行的回溯步骤,以便选择修订版本的预期下一步3.6证明控制在λCLA M和ISA PLANNER中,方法用于将方法组合成方法表达式。然后将方法表达式meth(M1,M2)解释为先应用方法M1,然后应用方法M2,如果 M1 适 用 的 话 . 例 如 , 方 法 论 表 达 了 一 个 证 明 的 结 构 , 那 么 meth(rewrite,orelse meth(assumption,tautology))控制一个证明,这个证明将试图重写一个目标,然后使用假设的证明方法或通过显示目标是一个重言式来证明它。方法表达了一个计划,证明搜索应该如何从这一点上取得进展。实际上,他们限制可能的规划运营商考虑在任何一点的证明搜索。方法表达式可以由证明计划操作符和其他方法表达式组成。这允许构造和重用操作符和这些复合控件。方法表达式也可以用来抽象证明计划:由方法表达式引入的方法的子树可以收缩为具有方法表达式作为证明的边方法表达式作为延续存储在规划状态中,并且延续随着规划的进展而修改(例如,在上面的例子中,一旦重写方法被应用,延续就变成了一种方法(假设,重言式)。在106洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93λCLA M用户在计划开始时以固定语言提供适当的方法表达式,系统将其解释为计划进步。ISA PLANNER将方法论视为证明规划运营商,可以由用户编程,以类似于λCLA M中使用的但完全可扩展的方式工作。在IBM MEGA中,方法的选择由控制规则控制。控制规则存在于规划算法的不同选择点:目标、证明方法和动作(实例化方法)。在这些选择点,规划者必须从规划状态中的对象列表中选择一个对象,以便继续。控制规则由条件组成,并在条件成立时修改给定的对象列表。控制规则在对象的初始列表上执行,该列表被过滤并重新排序以形成一个新的规划国家。稍后,规划器按照给定的顺序处理对象列表。控制规则的条件部分分析证明计划和证明历史。我们可以说,有条理的表达式表达了证明尝试的“未来”。而控制规则通过分析历史和证明计划来查看在IBM中,有一个额外的策略层。引入策略是因为拥有一组非结构化的方法和控制规则是不方便的。策略是方法和控制规则的集合,并提供隐式证明结构。一次验证规划尝试可能采用几种策略。这在概念上与一个有条理的表达式可以由其他表达式组成的方式类似。战略的选择受战略控制规则的控制还有一些控制规则可以中断策略。以方法论的形式表达证明控制的语言等价于交互式定理证明中的策略。有条理的表达式表示搜索模式。此模式的一个实例是具体定理的证明计划。策略中包含的当前方法和控制规则集显然也编码了证明模式,但不如方法论那样明确。特别是,修改和添加控制规则的效果很难预测,因为控制规则通过它们修改的选项列表进行交互。讽刺的是,在采用更具声明性的方法来构建证明方法的同时,IBM使用了一种不那么声明性的方法来控制知识。我们相信,在控制规则可以模仿有条理的表达式的解释和控制规则可以模仿有条件的方法时,有条理的方法具有相同的表达能力。5因此,方法的不同之处仅在于证明的风格。五是进一步做好工作,做好准备。洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93107控制被表达出来。例如,可以表示在每个方法应用之后,应尝试使用一个控制规则的简化方法。要用方法论来表达同样的行为,就需要在方法论表达式中的所有证明方法中增加简化方法。另一方面,用控制规则来表达一系列证明方法是相对麻烦的,而用有条理的then方法则是直截了当的。这两种方法的结合将利用不同风格的各自好处,构成进一步的工作。3.6.1启发式知识在大规模的证明方法表示尽可能一般,而启发式信息被委托给控制规则。这意味着通过调整这些控制规则,方法可以在各种不同的情况下重用。这也意味着不需要的方法应用在控制级被拒绝,而不是在方法的设计中编码这个决定。这种分离的结果是,对于不同的情况,必须实施不同的控制规则来应用相同的方法。λCLA M和ISA PLANNER并没有清楚地做出这种区分。潜在这可以导致一个证明步骤具有若干不同的实例作为具有不同的启发式前提集合的证明方法,这取决于它在方法表达式中的使用位置。在方法中包含方法学可能会使方法表达式的构造更简单。在证明方法中放置启发式知识降低了可重用性,但似乎允许证明控制更具声明性。如何将这种区分方法与启发式知识和法律知识的分离直接进行比较并不明显,我们计划进一步探索这一领域。3.7规划算法在所考虑的三个系统中,OMEGA采用了最复杂的规划算法,也是唯一一个可与AI规划系统相媲美的系统。对于控制规则的结果,Omega使用深度优先搜索策略,但该算法要经过几个首先,使用相关控制规则来选择要考虑的当前目标。然后,使用它们来选择适当的方法,并在选定的目标上解释和测试该方法。如果它是适用的,则验证计划、约束存储和历史被更新,并且过程重新开始。λCLA M使用的算法解释了有条理的结构,直到它涉及到第一个证明方法或批评家。如果这是适用的,则其被应用以创建新的计划状态,并且搜索根据证明控制继续。解释通常使用深度优先搜索。108洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93方法论的解释与战术的解释没有很大的不同,除了它在一个系统中工作,该系统包含用于证据搜索和证据修订的额外上下文信息。ISA PLANNER推理状态的议程可以由允许规划器在搜索策略之间切换这种力量尚未得到适当的评估,但它似乎与使用控制规则来选择下一个适当的目标、方法或行动没有根本的不同。4讨论和今后的工作我们将证明方法归类为描述目标和上下文操作的操作,这表明可能存在仅对上下文起作用的证明方法。考虑对象语言中不可能的表示,例如图表。这些可以在上下文中表现出来,而图解推理则相当于只操纵上下文的证明方法。这种证明上下文的使用将需要进一步澄清上下文信息的不同类型和上下文的结构。我们的分析还提出了一些问题,在何种程度上的陈述性是可取的证明方法和证明控制,并在何种程度上应鼓励用户分开法律和启发式信息。在进一步研究这些问题时需要解决的一个关键问题是,在多大程度上可以用一种类型的操作者模仿另一种类型的操作者的行为。我们在这方面的初步工作表明,这在两个方向都是可能的。因此,方法论和控制规则是同一知识的两种表示。我们的直接目的是更详细地探讨这些关于力量和表现力的问题。我们已经提出了一个框架的规划状态,证明语言,证明计划,证明方法,证明修订,证明控制和规划算法方面的证明规划的讨论。我们表明,这些类别都足以描述现代证明规划系统的所有显着特征,并在它们允许相似与相似进行比较(即使面对混乱和过载的术语)方面具有启发性。作为一个案例研究,我们已经将我们的框架应用到三个现代的证明规划系统,ISA PLANNER,λCLA M。这表明,校样规划器设计中的关键领域是校样控制和上下文信息的性质。我们希望在未来的工作中探索这些设计问题。洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93109梅加λCLA MISA PLANNER校对计划状态目标、证明计划、控制信息(控制规则)、证明上下文(约束存储)、历史验 证 计 划 、 控 制信 息 ( 续 ) 、 验证内容(注释)验证计划、控制信息(续)、验证内容校对语言高阶自然演绎型λ演算λcalculus各种我SABELLE逻辑证明计划DAG,扩展验证树,原则上推迟核查交错验证树证明方法带槽的声明性对象:输入、输出、参数、前提条件推理技术子集(decla-rativity)槽固定,解释语言的先决条件槽固定,编程语言的先决条件槽不固定,可选的前提条件-在上下文中的类似语句校样修订战略控制规则决定如何对失败失败方法/证明计划的证明批评家证明控制控制规则、战略和战略控制规则固定的方法语言来组合方法组合方法的可扩展方法语言(启发式知识)启发式知识不是在证明方法中而是在控制规则启发式知识在证明方法中,而不是在控制规则规划算法深度优先搜索证明方法可以改变局部搜索策略A表1ALUMMEGA、λCLM和ISA PLANNER一览。引用[1] A.邦迪 使用明确的计划来指导归纳证明。 E. Lusk和R. Overbeek,eds,CADE-9,LNCS 310,pp. 111-120. 一九八八年110洛杉矶Dennis等人/理论计算机科学电子笔记151(2006)93[2] A. 邦迪数学归纳法的自动化证明A. 罗宾逊和A. Voronkov,eds,Handbook of Automated Reasoning,Elsevier,2001。[3] A.邦迪对证据计划的批评。A. C. Kakas和F. Sadri ,eds,Computational Logic:LogicProgramming and Beyond,Essays in Honour of Robert A. Kowalski,LNCS 2408,pp.160-177. 2002年。[4] A. Cohen,S.默里,M。Pollet和V. Sorge。证明置换群问题的解。In F. Baader,编,CADE-19,LNAI 2741,pp. 258-273. 2003年。[5] L. Dixon和J. D.弗勒里奥 IsaPlanner:Isabelle中的原型证明规划器。 F.巴德,艾德,CADE-19,LNCS 2741,pp. 279-283. 2003年。[6] A. 爱尔兰 计划批评在归纳证明机械化中的应用。A. 沃龙科夫编辑,LPAR,LNAI 624,pp. 178-189. 一九九二年[7] A. 迈 耶 , M 。 Pollet 和 V. Sorge 。 剩 余 类 域 探 索 的 比 较 方 法 。 JSC , Special Issue on theIntegration of Automated Reasoning and Computer Algebra Systems,34(4):287-306,2002。S. Linton和R. Edinburgh,eds.[8] E. Melis和J.H.西克曼基于知识的证据规划。Arti ficial Intelligence,115(1):65[9] 欧米茄集团。开发人员:Dummega。A. Voronkov,ed,CADE-18,LNAI 2392,pp. 144[10] L. C.保尔森 Isabelle:一个通用的定理证明器。 LNCS 828. 一九九四年[11] J. D. C.理查森,A.斯梅尔和我共享的系统描述:用AMDACLAM进行高阶逻辑中的证明规划. C.Kirchner和H. Kirchner,eds,CADE-15,LNCAI 1421,pp. 129-133. 1998年
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功