On behavior of two-dimensional cellular automata with an exceptional rule

Several studies [A.R. Khan, P.P. Choudhury, K. Dihidar, S. Mitra, P. Sarkar, VLSI architecture of a cellular automata, Comput. Math. Appl. 33 (1997) 79-94; A.R. Khan, P.P. Choudhury, K. Dihidar, R. Verma, Text compression using two-dimensional cellular automata, Comput. Math. Appl. 37 (1999) 115-127; K. Dihidar, P.P. Choudhury, Matrix algebraic formulae concerning some exceptional rules of two-dimensional cellular automata, Inf. Sci. 165 (2004) 91-101] have explored a new rule convention for two-dimensional (2-D) nearest neighborhood linear cellular automata (CA) with null and periodic boundary conditions. A variety of applications of the rule convention have been illustrated, and the VLSI architecture of cellular automata machine (CAM) has been proposed. However, most of the studies address the issue of the kernel dimension of 2-D CA, and many other important characteristics of CA, such as Garden of Eden (GOE), maximal transient length, maximal cycle length, etc., have not been explored. In this paper, by exploiting matrix algebra in GF(2) (the Galois field with two elements), we attempt to characterize the behavior of a specific rule, which is not covered in existing work but accords with the same convention. A necessary and sufficient condition is given to ensure that a given configuration is a GOE. Meanwhile, we propose some algorithms to determine the number of GOEs, the maximal transient length, and the maximal cycle length in a 2-D CA.     

Reachable set bounding for delayed systems with polytopic uncertainties: The maximal Lyapunov-Krasovskii functional approach

This paper deals with the problem of reachable set estimation for time delay systems subject to both polytopic parameter uncertainties and bounded peak inputs. The maximal Lyapunov-Krasovskii functional is constructed as the pointwise maximum of a family of Lyapunov-Krasovskii functionals. Each functional corresponds to a vertex of uncertain polytope. Some criteria bounding the reachable set are derived. This approach shows great advantages over the traditional methods based on the common Lyapunov functionals. By introducing a modified integral inequality, the limitation imposed on the derivative of time delay being less than one is relaxed. Furthermore, the obtained results involve less computational burden when the number of vertices of the polytope is small. Two examples are given to illustrate the theoretical results.     

Interactive image segmentation by maximal similarity based region merging

Efficient and effective image segmentation is an important task in computer vision and object recognition. Since fully automatic image segmentation is usually very hard for natural images, interactive schemes with a few simple user inputs are good solutions. This paper presents a new region merging based interactive image segmentation method. The users only need to roughly indicate the location and region of the object and background by using strokes, which are called markers. A novel maximal-similarity based region merging mechanism is proposed to guide the merging process with the help of markers. A region R is merged with its adjacent region Q if Q has the highest similarity with Q among all Q's adjacent regions. The proposed method automatically merges the regions that are initially segmented by mean shift segmentation, and then effectively extracts the object contour by labeling all the non-marker regions as either background or object. The region merging process is adaptive to the image content and it does not need to set the similarity threshold in advance. Extensive experiments are performed and the results show that the proposed scheme can reliably extract the object contour from the complex background.     

k-匿名方法中相关视图集和准标识符的求解算法

准标识符是影响k-匿名方法有效性的关键因素.在视图发布过程中,求解准标识符所面临的问题是如何在已发布的视图集合中找出与待发布视图相关的全部视图.将已发布的视图集合与待发布的视图映射为一个超图,寻找相关视图集问题可被转化为在超图中求解特定结点间的全部通路问题.首先,给出了视图集向超图的映射方法及有关引理和定理,提出了基于超图的相关视图集求解算法;其次,研究了基本表中属性间不存在函数依赖和存在函数依赖两种情况下准标识符的组成结构,归纳出它们的特征,在此基础上,给出了基于相关视图集的准标识符求解算法.最后,对所提算法进行了正确性证明和时间复杂度分析.     

基于FPMAX的最大频繁项目集挖掘改进算法

挖掘事务数据库中的最大频繁项目集是数据挖掘领域一个重要的研究方向。基于FP-tree的FPMAX算法是目前较为高效与稳定的最大频繁项目集挖掘算法之一。然而对于稠密数据库中的挖掘,FPMAX会产生大量的冗余递归过程,导致额外的条件FP-tree构造开销。而且在支持度较低时,FPMAX则会因用于超集检测的全局MFI-tree较为庞大而导致超集检测的性能下降。为此提出FPMAX的改进算法FPMAX-reduce,其通过采用基于事务共同后缀的前瞻剪枝策略来减少挖掘过程中的冗余递归过程。 当递归过程中产生的新条件FP-tree规模较小时,FPMAX-reduce通过构造条件MFI-tree来减小后续超集检测遍历的开销。性能试验表明,FPMAX-reduce算法通过有效的前瞻剪枝,在稠密事务数据库以及低支持度的情况下至多可将递归过程减少至原算法的一半以下,进而有效地提高了FPMAX算法的效率。     

事件超图模型及类型识别

为避免向量空间模型的独立性假设影响事件类型识别,该文提出了一种基于超图的事件类型识别方法。该方法首先用事件超图描写事件元素间的多元有序关系;然后用事件超图模型(由事件超图添加类型组件和层面组件后构成)描述某个(某类)事件在不同观测层面的属性及其结构;最后根据事件的属性及其结构计算其相似度,并借此完成事件类型识别。实验结果显示,此方法识别效率的平均F值达到83.0%,与基于向量空间模型的支持向量机方法和最大熵方法相比,此方法也具有一定优势。     

轨迹和多标签超图配对融合的视频复杂事件检测

视频数据中包含丰富的运动事件信息,从中检测复杂事件,分析其中的高层语义信息,已成为视频研究领域的热点之一。视频复杂事件检测,主要对事件中多语义概念进行检测分析,对多运动目标的特征进行描述,发现底层特征与高层语义概念间的关系,旨在从各类视频特征及相关的原始视频数据中自动提取视频复杂事件中语义概念模式,实现“跨越语义鸿沟”的目标。在超图理论的基础上,提出了针对运动目标特征分别构建轨迹超图和多标签超图,并对其进行配对融合,用于检测视频复杂事件。实验结果证明,同其他方法如基于普通图的事件检测方法和基于超图的多标签半监督学习方法相比,新方法在检测复杂事件结果中具有更高的平均查准率和平均查全率。     

Maximally Concurrent Programs

Typically, program design involves constructing a program P that implements a given specification S; that is, the set ${\overline P}$ of executions of P is a subset of the set ${\overline S}$ of executions satisfying S. In many cases, we seek a program P that not only implements S, but for which ${\overline P}$ = ${\overline S}$. Then, every execution satisfying the specification is a possible execution of the program; we then call P maximal for the specification S. We argue that maximality is an important criterion in the context of designing concurrent programs because it disallows implementations that do not exhibit enough concurrency. In addition, a maximal solution can serve as a basis for deriving a variety of implementations, each appropriate for execution on a specific computing platform. This paper also describes a method for proving the maximality of a program with respect to a given specification. Even though we prove facts about possible executions of programs, there is no need to appeal to branching time logics; we employ a fragment of linear temporal logic for our proofs. The method results in concise proofs of maximality for several non-trivial examples. The method may also serve as a guide in constructing maximal programs. Received September 1997 / Accepted in revised form May 2000     

基于等价类和最大完全图集聚类的关联规则发现算法

关联规则的发现是数据挖掘中的一个重要问题,本文提供了一个基于等价类和最大完全图集聚类的关联规则的发现算法。