RCC11复合表的表示

主要研究熟知的区域连接演算(region connection calculus,简称RCC)的关系代数方面的性质.证明了补闭圆盘代数恰好构成RCC11复合表的一个表示,其中,RCC11复合表是由D(u)ntsch于1999年引入的.补闭圆盘代数由两类区域构成:一类是实平面中的所有闭圆盘;另一类是实平面中的所有闭圆盘的补的闭包组成.而连接关系为经典的Whiteheadean连接,即对区域a,b,aCb(表示a,b有连接关系)当且仅当 a∩b≠? .     

结合方向关系和拓扑关系的约束满足推理

结合定性空间推理中的区域连接演算(RCC)和基于区域的主方向关系模型,应用拓扑和方向关系上的复合表,将方向关系和拓扑关系的推理看作约束满足问题(CSP),给出了结合RCC8和主方向关系的约束满足问题推理算法,该算法可结合拓扑关系和方向关系进行推理。     

基于区域伸缩的空间关系研究与实现

区域连接演算(RCC)是空间推理的重要基础理论之一,它只能粗略地描述空间拓扑关系,难以描述除拓扑关系之外的其他空间关系,如距离和方向。在RCC理论的基础上,引入2个对区域的演算函数,即区域延伸和区域收缩,给出一种以区域为单位的形式化的度量方法。在RESC理论的基础上,利用栅格区域法应用简单和易于实现的特性,准确地得出区域间的空间关系。     

基于区域伸缩的空间关系表示

区域连接演算(RCC)是定性空间推理的重要基础理论之一.但由于缺乏必要的度量,RCC只是粗略地描述空间拓扑关系而难以对其更准确地描述,也难以利用RCC描述除拓扑关系之外的其它空间关系,如距离、方向等.本文在RCC理论的基础上,提出了区域伸缩演算(RESC).RESC增加了一个全等CG的原始空间关系,引入了两个新颖的对区域的演算函数,即区域延伸和区域收缩,从而给出了一种以区域为单位的形式化的度量方法.利用RESC,不仅可以扩展RCC-8拓扑关系,而且能以灵活多样的粒度来描述区域间的距离关系、方向关系、位置关系以及运动关系.RESC增强了RCC的空间关系表示能力,拓展了RCC理论的适用范围.     

Seven layers of knowledge representation and reasoning in supportof software development

The authors' experience in the Programmer's Apprentice project in applying knowledge representation and automated reasoning to support software development is summarized. A system, called Cake, is described that comprises seven layers of knowledge representation and reasoning facilities: truth maintenance, Boolean constraint propagation, equality, types, algebra, frames, and Plan Calculus. Sessions with two experimental software development tools implemented using Cake, the Requirements Apprentice and the Debugging Assistant, are also included     

Relation-algebraic semantics

The first half is a tutorial on orderings, lattices, Boolean algebras, operators on Boolean algebras, Tarski's fixed point theorem, and relation algebras.

In the second half, elements of a complete relation algebra are used as “meanings” for program statements. The use of relation algebras for this purpose was pioneered by de Bakker and de Roever in [10–12]. For a class of programming languages with program schemes, single μ-recursion, while-statements, if-then-else, sequential composition, and nondeterministic choice, a definition of “correct interpretation” is given which properly reflects the intuitive (or operational) meanings of the program constructs. A correct interpretation includes for each program statement an element serving as “input/output relation” and a domain element specifying that statement's “domain of nontermination”. The derivative of Hitchcock and Park [17] is defined and a relation-algebraic version of the extension by de Bakker [8, 9] of the Hitchcock-Park theorem is proved. The predicate transformers wp_s(-) and wlp_s(-) are defined and shown to obey all the standard laws in [15]. The “law of the excluded miracle” is shown to hold for an entire language if it holds for that language's basic statements (assignment statements and so on). Determinism is defined and characterized for all the program constructs. A relation-algebraic version of the invariance theorem for while-statements is given. An alternative definition of intepretation, called “demonic”, is obtained by using “demonic union” in place of ordinary union, and “demonic composition” in place of ordinary relational composition. Such interpretations are shown to arise naturally from a special class of correct interpretations, and to obey the laws of wp_s(-).     

A Comparison of Inferences about Containers and Surfaces in Small-Scale and Large-Scale Spaces

Inference mechanisms about spatial relations constitute an important aspect of spatial reasoning as they allow users to derive unknown spatial information from a set of known spatial relations. When formalized in the form of algebras, spatial-relation inferences represent a mathematically sound definition of the behavior of spatial relations, which can be used to specify constraints in spatial query languages. Current spatial query languages utilize spatial concepts that are derived primarily from geometric principles, which do not necessarily match with the concepts people use when they reason and communicate about spatial relations. This paper presents an alternative approach to spatial reasoning by starting with a small set of spatial operators that are derived from concepts closely related to human cognition. This cognitive foundation comes from the behavior of image schemata, which are cognitive structures for organizing people's experiences and comprehension. From the operations and spatial relations of a small-scale space, a container–surface algebra is defined with nine basic spatial operators—inside, outside, on, off, their respective converse relations—contains, excludes, supports, separated_from, and the identity relation equal. The container–surface algebra was applied to spaces with objects of different sizes and its inferences were assessed through human-subject experiments. Discrepancies between the container–surface algebra and the human-subject testing appear for combinations of spatial relations that result in more than one possible inference depending on the relative size of objects. For configurations with small- and large-scale objects larger discrepancies were found because people use relations such as part of and at in lieu of in. Basic concepts such as containers and surfaces seem to be a promising approach to define and derive inferences among spatial relations that are close to human reasoning.     

On the Relative Soundness of the Free Algebra Model for Public Key Encryption

Formal systems for cryptographic protocol analysis typically model cryptosystems in terms of free algebras. Modeling the behavior of a cryptosystem in terms of rewrite rules is more expressive, however, and there are some attacks that can only be discovered when rewrite rules are used. But free algebras are more efficient, and appear to be sound for “most” protocols. In [J. Millen, “On the freedom of decryption”, Information Processing Letters 86 (6) (June 2003) 329–333] Millen formalizes this intuition for shared key cryptography and provides conditions under which it holds; that is, conditions under which security for a free algebra version of the protocol implies security of the version using rewrite rules. Moreover, these conditions fit well with accepted best practice for protocol design. However, he left public key cryptography as an open problem. In this paper, we show how Millen's approach can be extended to public key cryptography, giving conditions under which security for the free algebra model implies security for the rewrite rule model. As in the case for shared key cryptography, our conditions correspond to standard best practice for protocol design.     

Connectivity in the regular polytope representation

In order to be able to draw inferences about real world phenomena from a representation expressed in a digital computer, it is essential that the representation should have a rigorously correct algebraic structure. It is also desirable that the underlying algebra be familiar, and provide a close modelling of those phenomena. The fundamental problem addressed in this paper is that, since computers do not support real-number arithmetic, the algebraic behaviour of the representation may not be correct, and cannot directly model a mathematical abstraction of space based on real numbers. This paper describes a basis for the robust geometrical construction of spatial objects in computer applications using a complex called the “Regular Polytope”. In contrast to most other spatial data types, this definition supports a rigorous logic within a finite digital arithmetic. The definition of connectivity proves to be non-trivial, and alternatives are investigated. It is shown that these alternatives satisfy the relations of a region connection calculus (RCC) as used for qualitative spatial reasoning, and thus introduce the rigor of that reasoning to geographical information systems. They also form what can reasonably be termed a “Finite Boolean Connection Algebra”. The rigorous and closed nature of the algebra ensures that these primitive functions and predicates can be combined to any desired level of complexity, and thus provide a useful toolkit for data retrieval and analysis. The paper argues for a model with two and three-dimensional objects that have been coded in Java and which implement a full set of topological and connectivity functions which is shown to be complete and rigorous.     

线型物体主方向关系推理的研究

线型物体主方向关系的推理研究是空间方向关系推理中的重要组成部分.在分析线型物体主方向关系模型的基础上,提出了线型物体主方向关系的投影区间矩形代数方法,从而实现了线型物体主方向关系的合理表示、基本推理运算以及线型物体主方向关系的凸关系判断.结合凸关系网络定理和路径一致性算法,提出了线型物体主方向关系网络一致性检验算法,给出了算法的正确性证明.