Reachability determination in acyclic Petri nets by cell enumeration approach

Reachability is one of the most important behavioral properties of Petri nets. We propose in this paper a novel approach for solving the fundamental equation in the reachability analysis of acyclic Petri nets, which has been known to be NP-complete. More specifically, by adopting a revised version of the cell enumeration method for an arrangement of hyperplanes in discrete geometry, we develop an efficient solution scheme to identify firing count vector solution(s) to the fundamental equation on a bounded integer set, with a complexity bound of O((nu)^n−m), where n is the number of transitions, m is the number of places and u is the upper bound of the number of firings for all individual transitions.     

On the estimation of adequate test set size using fault failure rates

Test set size in terms of the number of test cases is an important consideration when testing software systems. Using too few test cases might result in poor fault detection and using too many might be very expensive and suffer from redundancy. We define the failure rate of a program as the fraction of test cases in an available test pool that result in execution failure on that program. This paper investigates the relationship between failure rates and the number of test cases required to detect the faults. Our experiments based on 11 sets of C programs suggest that an accurate estimation of failure rates of potential fault(s) in a program can provide a reliable estimate of adequate test set size with respect to fault detection and should therefore be one of the factors kept in mind during test set construction. Furthermore, the model proposed herein is fairly robust to incorrect estimations in failure rates and can still provide good predictive quality. Experiments are also performed to observe the relationship between multiple faults present in the same program using the concept of a failure rate. When predicting the effectiveness against a program with multiple faults, results indicate that not knowing the number of faults in the program is not a significant concern, as the predictive quality is typically not affected adversely.     

Guarding a set of line segments in the plane

We consider the following problem: Given a finite set of straight line segments in the plane, find a set of points of minimum size, so that every segment contains at least one point in the set. This problem can be interpreted as looking for a minimum number of locations of policemen, guards, cameras or other sensors, that can observe a network of streets, corridors, tunnels, tubes, etc. We show that the problem is strongly NP-complete even for a set of segments with a cubic graph structure, but in P for tree structures.     

一个基于加权和组合降维的web文本分类系统

设计了一个web文本分类系统,采用了基于统计分析和粗糙集组合的方法进行降维;降维时考虑了属性的位置信息,采用加权方式标注属性的不同重要性,以达到提高分类速度和分类准确度的目的。     

Combinatorial optimization under uncertainty

In this paper, the general problem of Euclidean combinatorial optimization under uncertainty is formulated for the first time and the concepts of a stochastic multiset, a multiset of fuzzy numbers, a stochastic Euclidean combinatorial set, and general Euclidean combinatorial set of fuzzy stochastic numbers that combines the properties of both types of uncertainty are introduced. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 35–44, September–October 2008.     

Emotional agent based on rough set

To improve the ability of agent for handling emotions, a new architecture for emotion agent is presented, based on the traditional BDI agent model and the rough set theory. By a new emotional reasoning algorithm based on rough set, the architecture performs emotion reasoning and implements the emotion treatment. An emotional agent grid based on this architecture has been realized, experiment results show that it is efficient to transact simple emotions by emotional agents.     

轮廓字网格编织带修饰效果的实现

利用计算机进行设计各种字形修饰效果一直是计算机图形学的重要内容之一.本文给出了在轮廓字表面上构造网格点,基于这些网格点进行Delaunay三角剖分,并转换为3-4网格,最后在网格上实现编织带修饰效果的具体实现方法.其中3-4网格由良构的四边形单元和少量辅助三角形单元构成,在其上实现了较好的编织带修饰的效果.     

Livelocks in parallel programs

This paper is the second of a two-part series exploring the subtle correctness criterion of the absence of livelocks in parallel programs. In this paper we are concerned with the issue of proving this correctness criterion. It is shown that livelocks are not preserved by reduction, implying that reduction cannot be used directly in proving the absence of livelocks. Two applicable proof techniques are also presented. One is based on the notion of establishing sufficient conditions for livelock-freedom; the other is an extension of the well-founded set method for proving termination in sequential programs.     

An iterative algorithm based on the piecewise linear system for solving bilateral obstacle problems

In this paper, we derive the piecewise linear system (PLS) associated with the bilateral obstacle problem and illustrate the equivalence between the linear system and finite-dimensional complementary problem. The existence and the uniqueness of the solution to the PLS are also demonstrated. Based on the PLS, a Picard iterative algorithm is proposed. The convergence analysis is given and examples are presented to verify the effectiveness of the method.     

水工混凝土结构裂缝成因挖掘的粗集方法研究

裂缝是水工混凝土结构常见病害之一,针对水工混凝土结构运行期的裂缝问题,应用粗集理论,结合实测资料,对裂缝产生的主要原因进行了系统地研究,提出了裂缝成因挖掘的粗集方法.