Efficient Detection of Channel Predicates in Distributed Systems

This paper discusses efficient detection of global predicates in a distributed program. Previous work in this area required predicates to be specified as a conjunction of predicates defined on individual processes. Many properties in distributed systems, however, use the state of channels, such as “the channel is empty,” or “there is a token in the channel.” In this paper, we introduce the concept of alinearchannel predicate and provide efficient centralized and distributed algorithms to detect any conjunction of local and linear channel predicates. The class of linear predicates is fairly broad. For example, classic problems such as detection of termination and computation of global virtual time are instances of conjunctions of linear channel predicates. Linear predicates can be functions of the number of messages in the channel, or can be based upon the actual contents of the messages. The main application of our results are in debugging and testing of distributed programs. For these applications it is important to detect thefirststate where some predicate is true. We show that this first state is uniquely defined if and only if linear predicates are used.     

Spatially enabled customer segmentation using a data classification method with uncertain predicates

Spatial attributes are important factors for predicting customer behavior. However, thorough studies on this subject have never been carried out. This paper presents a new idea that incorporates spatial predicates describing the spatial relationships between customer locations and surrounding objects into customer attributes. More specifically, we developed two algorithms in order to achieve spatially enabled customer segmentation. First, a novel filtration algorithm is proposed that can select more relevant predicates from the huge amounts of spatial predicates than existing filtration algorithms. Second, since spatial predicates fundamentally involve some uncertainties, a rough set-based spatial data classification algorithm is developed to handle the uncertainties and therefore provide effective spatial data classification. A series of experiments were conducted and the results indicate that our proposed methods are superior to existing methods for data classification.     

Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK)

In this article, I focus on the robustness of geometric programs (e.g., Delaunay triangulation, intersection between surfacic or volumetric meshes, Voronoi-based meshing …) w.r.t. numerical degeneracies. Some of these geometric programs require “exotic” predicates, not available in standard libraries (e.g., J.-R. Shewchuk’s implementation and CGAL). I propose a complete methodology and a sample Open Source implementation of a toolset (PCK: Predicate Construction Kit) that makes it reasonably easy to design geometric programs free of numerical errors. The C++ code of the predicates is automatically generated from its formula, written in a simple specification language. Robustness is obtained through a combination of arithmetic filters, expansion arithmetics and symbolic perturbation.As an example of my approach, I give the formulas and PCK source-code for the 4 predicates used to compute the intersection between a 3d Voronoi diagram and a tetrahedral mesh, as well as symbolic perturbations that provably escapes the corner cases. This allows to robustly compute the intersection between a Voronoi diagram and a triangle mesh, or the intersection between a Voronoi diagram and a tetrahedral mesh. Such an algorithm may have several applications, including surface and volume meshing based on Lloyd relaxation.     

论中国手语的分类词谓语

分类词谓语是手语中一种独特的语言现象。中国大陆学者对分类词谓语的研究刚开始涉足,尚未见到系统的研究报道。该文试图从语言学的角度对中国手语分类词谓语做了语义认知分析,首先结合Talmy的动态事件和代形词的分析,解释中国手语的分类词谓语现象,分析主体和背景的代形词如何形成以达到手语同时性和序列性要求,并由此确定主体代形词和背景代形词通常是由非运动的手形组成;另一方面也说明中国手语与汉语的相互影响,对“动作”和“位于”这两类的手语代形词做了较为详细的描述及分类。     

Propositional compositions of partial predicates

Compositions of partial predicates of the highest abstraction level that form the basis of infinitary propositional logics are defined and investigated. The compositions are completely described in terms of special algebras called Klee ne algebras, and a complete system of identities is constructed for such compositions. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 3–19, March–April, 2000.     

Automatic Generation of Invariants

When proving invariance properties of programs, one is faced with two problems. The first problem is related to the necessity of proving tautologies of the considered assertion language, whereas the second manifests itself in the need of finding sufficiently strong invariants. This paper focuses on the second problem and describes techniques for the automatic generation of invariants. The first set of these techniques is applicable to sequential transition systems and allows deriving so-called local invariants, i.e., predicates which are invariant at some control location. The second is applicable on networks of transition systems and allows combining local invariants of the sequential components to obtain local invariants of the global system.     

Detection of global predicates: Techniques and their limitations

Summary. We show that the problem of predicate detection in distributed systems is NP-complete. In the past, efficient algorithms have been developed for special classes of predicates such as stable predicates, observer independent predicates, and conjunctive predicates. We introduce a class of predicates, semi-linear predicates, which properly contains all of the above classes. We first discuss stable, observer independent and semi-linear classes of predicates and their relationships with each other. We also study closure properties of these classes with respect to conjunction and disjunction. Finally, we discuss algorithms for detection of predicates in these classes. We provide a non-deterministic detection algorithm for each class of predicate. We show that each class can be equivalently characterized by the degree of non-determinism present in the algorithm. Stable predicates are defined as those that can be detected by an algorithm with the most non-determinism. All other classes can be derived by appropriately constraining the non-determinism in this algorithm.     

Constructive Membership Predicates as Index Types

In the constructive setting, membership predicates over recursive types are inhabited by terms indexing the elements that satisfy the criteria for membership. In this paper, we motivate and explore this idea in the concrete setting of lists and trees. We show that the inhabitants of membership predicates are precisely the inhabitants of a generic shape type. We show that membership of x (of type T) in structure S, (x_TS) can not, in general, index all parts of a structure S and we generalize to a form ρS where ρ is a predicate over S. Under this scheme, (λx.True)S is the set of all indexes into S, but we show that not all subsets of indexes are expressible by strictly local predicates. Accordingly, we extend our membership predicates to predicates that retain state “from above” as well as allow “looking below”. Predicates of this form are complete in the sense that they can express every subset of indexes in S. These ideas are motivated by experience programming in Nuprl's constructive type theory and examining the constructive content of mechanically checked formal proofs involving membership predicates.     

点物体主方向关系的一致性检验

一致性检验问题是主方向关系推理中非常重要的基础理论问题,提出了一种利用欧几里德空间坐标图实施一致性检验的新方法。首先对研究的问题进行了定义,阐述了方向关系的坐标图表示方法,从而使得对点物体方向关系约束集的一致性检验就转化为检测图中是否存在环的问题,通过一致性判定、环的检测、实施方法这3个环节来具体实现。其算法的时间复杂度是O（n+e）,优于传统的O（n²）     

基于SPEC#的自动测试方法

测试是软件质量的直接保障,然而人工书写测试代码不但繁琐而且会带来很多问题,自动化的测试方法的研究仍然停留在理论阶段.基于(SPEC# NUnit)平台,提出了一种切实可行的面向对象软件的自动化测试方法.这种方法使用形式化谓词断言来作为标准判断测试成功与否,搜索测试用例空间,同时可以模拟对象中间状态,自动生成复杂数据的测试用例.这一平台的建立也使得测试应绝对反映设计,由设计来直接指导测试的思想成为可能.     

BWDSP104X多条件谓词编译优化

目前BWDSP104X编译器对程序中条件分支的处理是采用传统的谓词优化方法,及每条指令和一个谓词相关,只有当谓词为真时指令才被执行,但它存在的局限性是当涉及到多条件谓词时,并不能消除跳转分支,且多条件谓词之间可能存在控制依赖关系,不利于指令并行和指令流水. 因此在现有编译器框架下,针对传统谓词优化方法的不足之处,本文提出一种基于BWDSP104X体系结构下多条件谓词编译优化方法. 实验结果表明,与传统谓词优化方法相比,该优化算法在BWDSP104X编译器上能够取得平均5.62的加速比.     

基于Z规格说明的软件测试用例自动生成

提出了一种基于Ｚ规格说明的软件测试用例自动生成方法,通过对软件Ｚ规格说明的分析,找出描述软件输入、输出约束的线性谓词,经过经性谓词转换,线性谓词到线性不等式组的转换,找出区域边界顶点和边界附近的测试点等过程自动生成测试用例。同时还介绍了基于Ｚ规格说明的软件测试用例自动生成方法的实例,并通过一个实例进一步加以说明。     

On the use of words and fuzzy sets

This paper only tries to stimulate some reflections, by showing a possible way towards rethinking fuzzy sets from their roots. A rethinking that does not change the view that fuzzy sets are mathematical entities giving extension to predicates. In such a way that, if the predicates are precise, the corresponding new entities are nothing else than classical sets.What, perhaps, is a key idea is that the use of a predicate organizes, in some way, the universe of discourse. When this organization is a preorder, the extension or L-set, appears once a degree, numerical or not, but consistent with the organization, can be defined.The ultimate goal of those above mentioned reflections, provided they would be realized in the future, is to extend the current theories of fuzzy sets to wider areas of both language and reasoning. Our objective is to reach a better knowledge of the links between language and its representations for the progress of computing with words and perceptions.     

An approach to knowledge-driven segmentation

Use of knowledge in a multiresolution multipredicate representation of image data is considered for the purpose of object segmentation and classification. Techniques for producing multiresolution data in the same computational process, and for producing segmentations based on grey level, colour, texture and optical flow predicates, are illustrated. In particular the use of knowledge encapsulated in 2D models is considered for compact and distributed objects.     

Abstractions for hybrid systems

We present a procedure for constructing sound finite-state discrete abstractions of hybrid systems. This procedure uses ideas from predicate abstraction to abstract the discrete dynamics and qualitative reasoning to abstract the continuous dynamics of the hybrid system. It relies on the ability to decide satisfiability of quantifier-free formulas in some theory rich enough to encode the hybrid system. We characterize the sets of predicates that can be used to create high quality abstractions and we present new approaches to discover such useful sets of predicates. Under certain assumptions, the abstraction procedure can be applied compositionally to abstract a hybrid system described as a composition of two hybrid automata. We show that the constructed abstractions are always sound, but are relatively complete only under certain assumptions.     

Finding extrema with unary predicates

We consider the problem of determining the maximum and minimum elements of a setX={x₁...,x _n }, drawn from some finite universeU of real numbers, using only unary predicates of the inputs. It is shown that (n+ log¦U¦) unary predicate evaluations are necessary and sufficient, in the worst case. Results are applied to (i) the problem of determining approximate extrema of a set of real numbers, in the same model, and (ii) the multiparty broadcast communication complexity of determining the extrema of an arbitrary set of numbers held by distinct processors.     

Detection of weak unstable predicates in distributed programs

This paper discusses detection of global predicates in a distributed program. Earlier algorithms for detection of global predicates proposed by Chandy and Lamport (1985) work only for stable predicates. A predicate is stable if it does not turn false once it becomes true. Our algorithms detect even unstable predicates, without excessive overhead. In the past, such predicates have been regarded as too difficult to detect. The predicates are specified by using a logic described formally in this paper. We discuss detection of weak conjunctive predicates that are formed by conjunction of predicates local to processes in the system. Our detection methods will detect whether such a predicate is true for any interleaving of events in the system, regardless of whether the predicate is stable. Also, any predicate that can be reduced to a set of weak conjunctive predicates is detectable. This class of predicates captures many global predicates that are of interest to a programmer. The message complexity of our algorithm is bounded by the number of messages used by the program. The main applications of our results are in debugging and testing of distributed programs. Our algorithms have been incorporated in a distributed debugger that runs on a network of Sun workstations in UNIX     

VASA: An algebra for vague spatial data in databases

Many geographical applications deal with objects in space that cannot be adequately described by determinate, crisp spatial concepts because of their intrinsically indeterminate and vague nature. Geographical information systems and spatial database systems are currently unable to cope with this kind of data. To support the efficient representation, querying, and manipulation of vague spatial data in a database context, we present a formal data model called vague spatial algebra (VASA). This algebra comprises a set of vague spatial data types for vague points, vague lines, and vague regions together with a comprehensive collection of vague spatial operations and vague topological predicates. One of VASA's main benefits is that its formal framework is based on well known, general, and exact models of crisp spatial data types. This enables an exact definition of the vague spatial model since we can build upon an already existing theory of spatial data types. In particular, crisp spatial data types turn out to be a special case of their vague counterparts. In addition, our approach enables executable specifications for the operations, which can be immediately used as implementations. The article offers a precise and conceptually clean foundation for implementing a DBMS extension for vague spatial data and demonstrates the embedding of these new data types as attribute data types in a database schema as well as the incorporation of vague spatial operations and predicates into queries formulated in an SQL-like query language. All concepts have been verified in a prototype implementation.     

一种通用连接查询的重写方法

使用实视图进行查询优化的关键,是从实视图中找到执行代价较小的查询重写.本文提出了一种基于目标的方法,可以找到更多的候选方案,当查询的内置谓词只包含特征变量时该方法更加有效.在更多时候,它可以找到由Bucket算法找到的所有重写,而且更高效.