基于CWM的元数据集成中形式化推理技术的研究

在使用公共仓库元模型（CWM）进行元数据集成的过程中，参与集成的团体的不同经验以及描述数据的不同视角不可避免地带来元数据的冲突和冗余等问题，然而CWM的图形化特点使之缺乏精确的语义，所以如何在其上进行推理以自动发现这些问题至今没有得到很好的解决。本文研究了利用描述逻辑，一个一阶谓词逻辑的可判定子集，形式化CWM元模型和模型并进行推理的方法，将一致性检测分为水平一致性和演化一致性进行分别处理，在处理演化一致性的过程中对CWM元模型进行了扩展，使之支持元数据的版本能力从而能够推理由于演化引起的不一致问题，然后利用推理引擎LOOM对两种情形进行推理检测以发现不一致信息，取得了令人满意的结果，表明本文提出的方法是可行的。     

基于SHOIN（D）的UML类图形式化方法

UML模型一致性自动检测的主要任务是解决形式化问题。描述逻辑是一阶谓词逻辑的可判定子集,具备强大的知识表示和推理功能。针对UML模型形式化问题,提出基于描述逻辑的形式化方法,分析UML类图各模型元素与描述逻辑SHOIN（D）的对应关系,提出UML类图的SHOIN（D）形式化方法,给出UML类图转换为SHOIN（D）知识库的正确性证明。     

Expressiveness and complexity of graph logic

We investigate the complexity and expressive power of a spatial logic for reasoning about graphs. This logic was previously introduced by Cardelli, Gardner and Ghelli, and provides the simplest setting in which to explore such results for spatial logics. We study several forms of the logic: the logic with and without recursion, and with either an exponential or a linear version of the basic composition operator. We study the combined complexity and the expressive power of the four combinations. We prove that, without recursion, the linear and exponential versions of the logic correspond to significant fragments of first-order (FO) and monadic second-order (MSO) Logics; the two versions are actually equivalent to FO and MSO on graphs representing strings. However, when the two versions are enriched with μ-style recursion, their expressive power is sharply increased.Both are able to express PSPACE-complete problems, although their combined complexity and data complexity still belong to PSPACE.     

Logic of transition systems

Labeled transition systems are key structures for modeling computation. In this paper, we show how they lend themselves to ordinary logical analysis (without any special new formalisms), by introducing their standard first-order theory. This perspective enables us to raise several basic model-theoretic questions of definability, axiomatization and preservation for various notions of process equivalence found in the computational literature, and answer them using well-known logical techniques (including the Compactness theorem, Saturation and Ehrenfeucht games). Moreover, we consider what happens to this general theory when one restricts attention to special classes of transition systems (in particular, finite ones), as well as extended logical languages (in particular, infinitary first-order logic). We hope that this puts standard logical formalisms on the map as a serious option for a theory of computational processes. As a side benefit, our approach increases comparability with several other existing formalisms over labeled transition systems (such as Process Algebra or Modal Logic). We provide some pointers to this effect, too.     

模糊描述逻辑系统L-ALCN中的形式概念格

该文首先简单介绍格值模糊描述逻辑系统L-ALCN的语法和语义,介绍形式概念分析(FCA)的基本理论。把形式概念分析引入到模糊描述逻辑中,在国际上也是刚刚起步,尚不成熟。该文定义了模糊形式背景、模糊形式概念格,并证明了此概念格为完备格。     

模糊描述逻辑系统L-ALCN中的形式概念格

该文首先简单介绍格值模糊描述逻辑系统L—ALCN的语法和语义,介绍形式概念分析（FCA）的基本理论。把形式概念分析引入到模糊描述逻辑中,在国际上也是刚刚起步,尚不成熟。该文定义了模糊形式背景、模糊形式概念格,并证明了此概念格为完备格。     

Natural Deduction for First-Order Hybrid Logic

This is a companion paper to Braüner (2004b, Journal of Logic and Computation 14, 329–353) where a natural deduction system for propositional hybrid logic is given. In the present paper we generalize the system to the first-order case. Our natural deduction system for first-order hybrid logic can be extended with additional inference rules corresponding to conditions on the accessibility relations and the quantifier domains expressed by so-called geometric theories. We prove soundness and completeness and we prove a normalisation theorem. Moreover, we give an axiom system first-order hybrid logic.     

Infinitary Logic and Inductive Definability over Finite Structures

The extensions of first-order logic with a least fixed point operator (FO + LFP) and with a partial fixed point operator (FO + PFP) are known to capture the complexity classes P and PSPACE respectively in the presence of an ordering relation over finite structures. Recently, Abiteboul and Vianu (in "Proceedings of the 23rd ACM Symposium on the Theory of Computing," 1991) investigated the relationship of these two logics in the absence of an ordering, using a machine model of generic computation. In particular, they showed that the two languages have equivalent expressive power if and only if P = PSPACE. These languages can also be seen as fragments of an infinitary logic where each formula has a bounded number of variables, L^ω_∞ω, (see, for instance, Kolaitis and Vardi, in "Proceedings of the 5th IEEE Symposium on Logic in Computer Science," pp. 156-167, 1990). We investigate this logic on finite structures and provide a normal form for it. We also present a treatment of Abiteboul and Vianu′s results from this point of view. In particular, we show that we can write a formula of FO + LFP that defines an ordering of the L^k_∞ω, types uniformly over all finite structures. One consequence of this is a generalization of the equivalence of FO + LFP and P from ordered structures to classes of structures where every element is definable. We also settle a conjecture mentioned by Abiteboul and Vianu by showing that FO + LFP is properly contained in the polynomial time computable fragment of L^ω_∞ω, raising the question of whether the latter fragment is a recursively enumerable class.     

First-Order Temporal Verification in Practice

First-order temporal logic, the extension of first-order logic with operators dealing with time, is a powerful and expressive formalism with many potential applications. This expressive logic can be viewed as a framework in which to investigate problems specified in other logics. The monodic fragment of first-order temporal logic is a useful fragment that possesses good computational properties such as completeness and sometimes even decidability. Temporal logics of knowledge are useful for dealing with situations where the knowledge of agents in a system is involved. In this paper we present a translation from temporal logics of knowledge into the monodic fragment of first-order temporal logic. We can then use a theorem prover for monodic first-order temporal logic to prove properties of the translated formulas. This allows problems specified in temporal logics of knowledge to be verified automatically without needing a specialized theorem prover for temporal logics of knowledge. We present the translation, its correctness, and examples of its use. Partially supported by EPSRC project: Analysis and Mechanisation of Decidable First-Order Temporal Logics (GR/R45376/01).     

语义web中以描述逻辑为本体语言的推理

语义Web是worldwideweb的发展方向,它的实现能有效地提高互联网的智能化程度,进而提高其使用效率。描述逻辑作为语义Web的一个逻辑基础,成为其研究和开发的重要内容。该文讨论了语义Web中以描述逻辑为本体语言的推理方法,并对其应用作了简要的分析。     

强表达描述逻辑本体的后继式公理定位研究

公理定位能够挖掘描述逻辑中可解释的缺陷,并为逻辑蕴含结果寻找隐藏的理由,因此在描述逻辑研究中引起了广泛的关注.平衡描述逻辑表达能力和推理机求解效率问题一直是公理定位研究的重点内容.本文基于一种后继式判定算法,从白盒和黑盒两个角度将其用于公理定位.白盒方法利用修正的后继式规则（即定位规则）来追踪推理的具体过程,并引入定位公式的概念建立子句的布尔公式标签与逻辑蕴含的所有极小公理集之间的对应关系.黑盒方法则直接调用基于未修正的后继式规则的推理机,并进一步利用碰集树方法求得逻辑蕴含的所有理由.最后,基于这样的两种面向强表达描述逻辑本体的公理定位算法设计推理工具,从理论和实验两方面验证其可行性,并与已有的推理工具比较求解性能.