Bounded Model Generation for Isabelle/HOL

A translation from higher-order logic (on top of the simply typed λ-calculus) to propositional logic is presented, such that the resulting propositional formula is satisfiable iff the HOL formula has a model of a given finite size. A standard SAT solver can then be used to search for a satisfying assignment, and such an assignment can be transformed back into a model for the HOL formula. The algorithm has been implemented in the interactive theorem prover Isabelle/HOL, where it is used to automatically generate countermodels for non-theorems.     

数理逻辑教学内容研究

数理逻辑是研究推理的数学分支,这部分内容概念抽象,方法灵活,学生很难理解和掌握。为了提高教学效果,研究数理逻辑的主要内容,即命题逻辑与一阶逻辑,分析两部分之间的内在联系及区别,并列举实例来说明它们的联系,在教学过程中始终把握住它们的关联性,可以明显提高教学效果。     

用于数字系统设计的函数式语言解析方案

介绍一种应用于数字系统设计中的基于函数式语言的代码解析方案,主要包括该函数式语言和解析工具的介绍,该语言的词法与语法分析程序的结构介绍,由语法树到语法规则到抽象语法树的生成过程,以及具体的应用实例。该解析方案已经成功应用于数字系统的设计中。     

基于Java的泛型编程

泛型编程是面向对象的进一步发展,从更高的角度对世界进行抽象,为面向对象的不足之处提供了解决之道.它可让你重复运用既有的算法,而不必在环境类似的情况下再重新撰写相同代码,使得处理的问题更加抽象化,是一种优美而又不失效率的通用型程序设计方法.JDK 1.5中引入了对Java语言的多种扩展,泛型(generics)即其中之一.本文讨论JDK 1.5的泛型实现.     

统计关系学习模型Markov逻辑网综述*

统计关系学习是人工智能研究的热点,在生物信息学、地理信息系统和自然语言理解等领域有着重要应用,Markov逻辑网是将Markov网与一阶逻辑相结合的一种全新的统计关系学习模型。介绍了Markov逻辑网的理论模型和学习方法,并探讨了目前存在的问题和研究方向。     

Statecharts的抽象语法分析研究

用抽象数据类型来描述Statecharts,希望隐藏语义表述上的细节,把一个图形化的语言转换为文本的方式来描述,并为Statecharts语法分析奠定基础。     

行为时序逻辑与自反线性时序逻辑的关系

为了能够将哲学逻辑中的公理系统运用到行为时序逻辑的研究中。对行为时序逻辑公式的语义进行形式化定义．从语义和语法两方面研究行为时序逻辑公理系统和具有自反性质的线性时序逻辑公理系统之间的联系．提出并证明行为时序逻辑公式转换为自反线性时序逻辑公式的定理。按照集合论和模型论的思想,定义行为时序逻辑中项和行为时序逻辑原子公式的概念。定义Lesilie Lamport所提出的行为时序逻辑公式的语义。证明自反线性时序逻辑公理系统适用于行为时序逻辑公理系统．以此为基础证明行为时序逻辑的简单规则、基本规则和附加规则。     

First-Order Glue

Glue has evolved significantly during the past decade. Although the recent move to type-theoretic notation was a step in the right direction, basing the current Glue system on System F (second-order λ-calculus) was an unfortunate choice. An extension to two sorts and ad hoc restrictions were necessary to avoid inappropriate composition of meanings. As a result, the current system is unnecessarily complicated. A first-order Glue system is hereby proposed as its replacement. This new system is not only simpler and more elegant, as it captures the exact requirements for Glue-style compositionality without ad hoc improvisations, but it also turns out to be more powerful than the current two-sorted (pseudo-) second-order system. First-order Glue supports all existing Glue analyses as well as more elegant alternatives. It also supports new, more demanding analyses.     

ECMAScript解释器的中间代码生成技术研究

论文详细介绍了在ECMAScript解释器中,中间代码生成部分的设计和实现方法。同时也简要介绍了解释器的整体结构。     

Compile-time analysis of nonlinear constraints in CLPR

Solving nonlinear constraints over real numbers is a complex problem. Hence constraint logic programming languages like CLPR or Prolog III solve only linear constraints and delay nonlinear constraints until they become linear. This efficient implementation method has the disadvantage that sometimes computed answers are unsatisfiable or infinite loops occur due to the unsatisfiability of delayed nonlinear constraint These problems could be solved by using a more powerful constraint solver which can deal with nonlinear constraints like in RISC-CLP(Real). Since such powerful constraint solvers are not very efficient, we propose a compromise between these two extremes. We characterize a class of CLPR programs for which all delayed nonlinear constraints become linear at run time. Programs belonging to this class can be safely executed with the efficient CLPR method while the remaining programs need a more powerful constraint solver. This paper is an extended and revised version of Ref. 12). The research described in this paper was made during the author’s stay at the Max-planck-Institut für Informatik in Saarbrücken, Germany. It was supported in part by the German Ministry for Research and Technology (BMFT) under grant ITS 9103 and by the ESPRIT Basic Research Working Group 6028 (Construction of Computational Logics). The responsibility for the contents of this publication lies with the author.     

面向对象技术在C编译器OCC中的应用

对面向对象的C编译器(OCC)的整体设计进行介绍。OCC以抽象语法树为中间表达形式。语法树节点分为8大类86种,降低了在采用visitor设计模式进行语意分析时节点功能的耦合度。OCC用简易的垃圾回收器解决了语法树节点动态分配和销毁时的内存泄漏问题。OCC的类型分析模块针对类型声明中9个不同组成部分采用7种处理方式,降低了属性文法脚本的维护难度。     

Agent心智状态形变理论和微分计算形式

本文抓住Agent的核心问题，借助范畴论思想，通过研究Agent心智状态形式化理论框架，建立了Agent心智状态形变理论及微分计算等基本概念。这些内容进一步丰富和发展了Agent的基本内容。     

Practical Reflection for Sequent Logics

It is well-known that adding reflective reasoning can tremendously increase the power of a proof assistant. In order for this theoretical increase of power to become accessible to users in practice, the proof assistant needs to provide a great deal of infrastructure to support reflective reasoning. In this paper we explore the problem of creating a practical implementation of such a support layer.Our implementation takes a specification of a logical theory (which is identical to how it would be specified if we were simply going to reason within this logical theory, instead of reflecting it) and automatically generates the necessary definitions, lemmas, and proofs that are needed to enable the reflected meta-reasoning in the provided theory.One of the key features of our approach is that the structure of a logic is preserved when it is reflected. In particular, all variables, including meta-variables, are preserved in the reflected representation. This also allows the preservation of proof automation—there is a structure-preserving one-to-one map from proof steps in the original logic to proof step in the reflected logic.To enable reasoning about terms with sequent context variables, we develop a principle for context induction, called teleportation.This work is fully implemented in the MetaPRL theorem prover.     

A first-order axiomatization of the theory of finite trees

We provide first-order axioms for the theories of finite trees with bounded branching and finite trees with arbitrary (finite) branching. The signature is chosen to express, in a natural way, those properties of trees most relevant to linguistic theories. These axioms provide a foundation for results in linguistics that are based on reasoning formally about such properties. We include some observations on the expressive power of these theories relative to traditional language complexity classes.The research reported in this paper has been supported by the Bundesminister für Forschung und Technologie under contract ITW 01 IV 101 K/1 (Verbmobil).Part of this work was done during the period when this author was at DFKI, Saarbrücken. This author would like to thank Prof. Dr. H. Uszkoreit and Prof. Dr. W. Wahlster for providing the facilities and a supportive environment.     

模型检验综述

在软硬件验证里,模型检验是一个重要手段,至今它已经形成一个庞大的方法论体系。现在我们把模型检验内容从标准方法、抽象解释方法、综合方法3个范畴加以介绍,旨在形成人们对模型检验总的印象,从而全面理解和掌握模型检验各个方法的精神实质和具体情况,有助于将这些方法运用到实际软硬件验证中并从中受到启发,以便进一步发展模型检验理论或开发模型检验新的方法和工具。     

安全协议的形式化分析方法研究

安全协议在网络信息安全中扮演着重要角色,但保证安全协议的正确是一个很困难的问题。现在,许多形式化方法都被用来分析安全协议,本文中我们研究各种方法的基本思想、它的优缺点、发展趋势以及方法之间的关系。最后,说明安全协议形式化分析的困难所在。     

Towards a logic programming methodology based on higher-order predicates

This paper outlines a logic programming methodology which applies standardized logic program recursion forms afforded by a system of general purpose recursion schemes. The recursion schemes are conceived of as quasi higher-order predicates which accept predicate arguments, thereby representing parameterized program modules. This use of higher-order predicates is analogous to higher-order functionals in functional programming. However, these quasi higher-order predicates are handled by a metalogic programming technique within ordinary logic programming. Some of the proposed recursion operators are actualizations of mathematical induction principles (e.g. structural induction as generalization of primitive recursion). Others are heuristic schemes for commonly occurring recursive program forms. The intention is to handle all recursions in logic programs through the given repertoire of higher-order predicates. We carry out a pragmatic feasibility study of the proposed recursion operators with respect to the corpus of common textbook logic programs. This pragmatic investigation is accompanied with an analysis of the theoretical expressivity. The main theoretical results concerning computability are

1. Primitive recursive functions can be re-expressed in logic programming by predicates defined solely by non-recursive clauses augmented with afold recursion predicate akin to the fold operators in functional programming.
2. General recursive functions can be re-expressed likewise sincefold allows re-expression of alinrec recursion predicate facilitating linear, unbounded recursion.