Elimination of Local Variables from Definite Logic Programs

In logic programming, a variable is said to be local if it occurs in a clause body but not in its head atom. It is well-known that local variables are the main cause of inefficiency (sometimes even incompleteness) in negative goal computation. The problem is twofold. First, the negation of a clause body that contains a local variables is not expressible without universal quantification, whereas the abscence of local variables guarantees that universal quantification can be avoided to compute negation. Second, computation of universal quantification is an intrinsically difficult task. In this paper, we introduce an effective method that takes a definite logic program and transforms it into a local variable free (definite) program. Source and target programs are equivalent w.r.t. three-valued logical consequences of program completion. In further work, we plan to extend our results to normal logic programs.     

On Isomorphism Testing of Groups with Normal Hall Subgroups

A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index.SchurZassenhaus theorem states that every normal Hall subgroup has a complement subgroup,that is a set of coset representatives H which also forms a subgroup of G.In this paper,we present a framework to test isomorphism of groups with at least one normal Hall subgroup,when groups are given as multiplication tables.To establish the framework,we first observe that a proof of Schur-Zassenhaus theorem is constructive,and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products,and isomorphisms of the normal parts and complement parts.We then focus on the case when the normal subgroup is abelian.Utilizing basic facts of representation theory of finite groups and a technique by Le Gall (STACS 2009),we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators.For the case when the complement subgroup is elementary abelian,which does not necessarily have bounded number of generators,we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem,which asks whether two linear subspaces are the same up to permutation of coordinates.A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai et al.(SODA 2011).Enroute to obtaining the above reduction,we study the following computational problem in representation theory of finite groups: given two representations ρ and τ of a group H over Zpd,p a prime,determine if there exists an automorphism φ : H → H ,such that the induced representation ρφ = ρφ and τ are equivalent,in time poly(|H |,pd).     

描述逻辑程序系统的设计与实现

Eiter等人为语义网提出的回答集程序和描述逻辑相结合的描述逻辑程序,获得了本体上的非单调表达和推理能力。王以松等人证明了描述逻辑程序的完备化和环公式可以精确刻画描述逻辑程序的回答集。在此基础上,进一步证明了若完备化公式的模型不是回答集则一定存在终止环公式反例,它们是多项式时间可计算的。设计并实现了借助SAT求解器MiniSAT以及描述逻辑推理机RacerPro计算描述逻辑强回答集的原型DLP_SAT。实验结果表明,该原型能有效地计算一些熟知的描述逻辑程序的强回答集。     

一个支持非独立“与”并行的逻辑程序“与”并行执行模型

本提出了一种支持非独立“与”并行的新型“与”并行执行模型ＤＡＰＭ，它通过在共享变元之间建立一种类似生产和消费的同步依赖关系以防止它们在并行执行时产生的约束冲突。与其它模型相比，ＤＡＰＭ可以开发更多的“与”并行。本还从理论上对ＤＡＰＭ的运行代价进行了分析，其分析结果表明ＤＡＰＭ只需较小的运行时刻支持。     

扩充析取逻辑程序的争论语义

该文探讨争论推理在扩充逻辑程序中的实现及其关系问题.基于“相干原理”,建立了扩充逻辑程序的争论推理框架,多种争论推理形式都可以嵌入其中.特别是提出了一种谨慎语义Acc.同时又定义了良基语义的一种合理扩充Mod,以处理较为大胆的推理形式.另外也研究了相关的理论性质.     

关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。     

基于分离逻辑的并行程序性质验证方法

随着多核多线程并行执行方式的普及,并行程序形式化验证的需求日显突出.并行程序验证中执行流程的不确定性使验证的内容与目标的关系难以确定,且从并行程序直接进行性质验证会导致验证规模大.为此,提出一种基于分离逻辑的新的验证方法.该方法根据分离逻辑的程序语义描述兼有解释语义和公理语义的特点,从验证的性质出发,把要验证的性质式转换成并行语句序列的逻辑组合式,并进行整理和化简;然后,利用分离逻辑公理系统对语句序列进行验证,用验证了的断言集来求出性质的真值.实例进一步说明,此方法更有效,同时也简化了验证的规模.     

带函数析取逻辑程序的无基集及其应用

基于回答集（也称稳定模型）语义的带函数析取逻辑程序是一种重要的知识表示和推理方法。由于判定一个析取逻辑程序是否有回答集是困难的（Σ2完全的）,目前还没有有效的方法来计算带函数析取逻辑程序的回答集,主要原因之一是检查一个集合是否是回答集是coNP完全的。提出了带函数析取逻辑程序无基集（unfounded sets）的概念,发现了空无基集（unfounded-free sets）与稳定模型之间的一一对应关系,在此基础上,证明了一个逻辑程序的模型是该程序的稳定模型当且仅当它们对应的一个命题公式是不可满足的,从而在理论上为计算带函数析取逻辑程序的回答集提供了一种有效的途径。     

Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

Program specialization is a program transformation methodology which improves program efficiency by exploiting the information about the input data which are available at compile time. We show that current techniques for program specialization based on partial evaluation do not perform well on nondeterministic logic programs. We then consider a set of transformation rules which extend the ones used for partial evaluation, and we propose a strategy for guiding the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which sometimes are exponential, are due to the reduction of nondeterminism and to the fact that the computations which are performed by the initial programs in different branches of the computation trees, are performed by the specialized programs within single branches. In order to reduce nondeterminism we also make use of mode information for guiding the unfolding process. To exemplify our technique, we show that we can automatically derive very efficient matching programs and parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.A preliminary version of this paper appears as: Reducing Nondeterminism while Specializing Logic Programs. Proceedings of the 24th Annual ACM Symposium on Principles of Programming Languages, Paris, France, January 15–17, 1997, ACM Press, 1997, pp. 414–427.     

The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F) = H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.     

The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F)=H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.     

一种用于指针程序验证的指针逻辑

本文改进并扩展先前为验证指针程序提出的指针逻辑,主要贡献是提出了合法访问路径集合的概念,极大地简化了访问路径上的基本运算,并使得指针逻辑推理规则变得易理解.另外,增加了局部推理规则和函数构造的推理规则,使得指针逻辑可以方便地用于有函数调用的场合.     

一种面向非干扰的线程程序逻辑

目前,针对线程信息流的验证研究主要着重于时间信道.然而,由于线程程序中线程控制原语存在函数副作用,对此类原语的不恰当调用亦可引起非法信息流,有意或无意地破坏程序的非干扰属性.因此,提出以验证线程程序信息流为目的依赖逻辑,其可表达线程程序的数据流、控制流以及线程控制函数的副作用,推理程序变量和线程标识符之间的依赖关系,进而判定是否存在高机密性变量对低机密性变量的干扰.     

Comparison of Semantics of Disjunctive Logic Programs Based on Model-Equivalent Reduction

In this paper, it is shown that stable model semantics, perfect model semantics, and partial stable model semantics of disjunctive logic programs have the same expressive power with respect to the polynomial-time model-equivalent reduction. That is, taking perfect model semantics and stable model semantic as an example, any logic program P can be transformed in polynomial time to another logic program P＇ such that perfect models （resp. stable models） of P i-i correspond to stable models （resp. perfect models） of P＇, and the correspondence can be computed also in polynomial time. However, the minimal model semantics has weaker expressiveness than other mentioned semantics, otherwise, the polynomial hierarchy would collapse to NP.     

格值有限状态自动机的同态和商自动机

提出了格值有限状态自动机（LFSA）的同态、强同态的概念,研究了LFSAs同态、强同态的若干性质。在LFSAs强同态的基础上,得到了LFSA的商自动机及其最小化自动机,刻画了商自动机的性质。     

Token-Templates and Logic Programs for Intelligent Web Search

We present a general framework for the information extraction from web pages based on a special wrapper language, called token-templates. By using token-templates in conjunction with logic programs we are able to reason about web page contents, search and collect facts and derive new facts from various web pages. We give a formal definition for the semantics of logic programs extended by token-templates and define a general answer-complete calculus for these extended programs. These methods and techniques are used to build intelligent mediators and web information systems.     

一种用于指针程序安全性证明的指针逻辑

在高可信软件的各种性质中,安全性是被关注的重点,其中软件满足安全策略的证明方法是研究的热点之一.文中根据作者所设想的安全程序的设计和证明框架,为类C语言的一个子集设计了一个指针逻辑系统.该逻辑系统是Hoare逻辑系统的一种扩展,它用推理规则来表达每一种语句引起指针信息的变化情况.它可用来对指针程序进行精确的指针分析,所获得的信息用来证明指针程序是否满足定型规则的附加条件,以支持程序的安全性验证.该逻辑系统也可用来证明指针程序的其它性质.