比特切片型算法差分及线性特征的快速构造

比特切片方法由Biham等人于1997年提出,该方法可以高效提升算法的软件实现性能,后来被广泛应用于Serpent、RECTANGLE、TANGRAM等分组算法.本文针对扩散层采用简单行循环移位的RECTANGLE、TANGRAM等比特切片型分组算法,根据算法S盒的性质以及行移位参数,给出了快速判断其是否存在单轮循环差分/线性特征的方法.基于找到的单轮循环差分/线性特征,结合MILP自动化搜索技术,实现了这类算法长轮数差分/线性特征的快速构造.进一步,我们扩展寻找单轮循环特征的思想,利用MILP方法自动化搜索了不超过4轮的循环差分/线性特征,基于此可以更方便构造长轮数差分/线性特征.利用此方法,我们找到了RECTANGLE算法的14轮差分特征和13轮线性特征, TANGRAM128算法的24轮差分特征和23轮线性特征, TANGRAM 256算法的48轮差分特征和44轮线性特征.特别地,我们找到的TANGRAM 256算法的44轮线性特征是目前找到的最长轮数的线性特征.我们的方法只依赖于算法的结构特点和S盒的性质,该研究对采用这种结构的分组算法长轮数差分/线性特征的寻找和相应算法的设计都有重要意义.     

Employing locality in the evolutionary generation of fuzzy rulebases

Fuzzy rule bases have proven to be an effective tool for modeling complex systems and approximating functions. The generation of a fuzzy rule base has generally been accomplished by a heuristic analysis of the relationships of the underlying system or by algorithmic rule generation from training data. Automatic rule generation has utilized clustering algorithms, proximity analysis, and evolutionary techniques to identify approximate relationships between the input and the output. In this research, two general approaches for the evolutionary generation of fuzzy rules are identified and compared: global and local rule generation. Global rule production, which is the standard method of employing evolutionary techniques in fuzzy rule base generation, considers an entire rule base as an element of population. The fitness evaluation of a rule base aggregates the performance of the model over the entire space into a single value. The local approach utilizes the limited scope of a fuzzy rule to evaluate performance in regions of the input space. The local generation of rule bases employs an independent evolutionary search in each region and combines the local results to produce a global model. An experimental suite has been developed to compare the effectiveness of the two strategies for the evolutionary generation of fuzzy models.     

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.     

An /spl epsiv/-margin nonlinear classifier based on fuzzy if-then rules

This paper introduces a new classifier design methods that are based on a modification of the classical Ho-Kashyap procedure. First, it proposes a method to design a linear classifier using the absolute loss rather than the squared loss that results in a better approximation of the misclassification error and robustness of outliers. Additionally, easy control of the generalization ability is obtained by minimization of the Vapnik-Chervonenkis dimension. Next, an extension to a nonlinear classifier by an ensemble averaging technique is presented. Each classifier is represented by a fuzzy if-then rule in the Takagi-Sugeno-Kang form. Two approaches to the estimation of parameters value are used: local, where each of the if-then rule parameters are determined independently and global where all rules are obtained simultaneously. Finally, examples are given to demonstrate the validity of the introduced methods.     

Genetic rule induction at an intermediate level

Lists of if–then rules (i.e. ordered rule sets) are among the most expressive and intelligible representations for inductive learning algorithms. Two extreme strategies searching for such a list of rules can be distinguished: (i) local strategies primarily based on a step-by-step search for the optimal list of rules, and (ii) global strategies primarily based on a one-strike search for the optimal list of rules. Both approaches have their disadvantages. In this paper we present an intermediate strategy. A sequential covering strategy is combined with a one-strike genetic search for the next most promising rule. To achieve this, a new rule-fitness function is introduced. Experimental results on benchmark problems are presented and the performance of our intermediate approach is compared with other rule learning algorithms. Finally, GeSeCo's performance is compared to a more local strategy on a set of tasks in which the information value of individual attributes is varied.     

Mining optimized gain rules for numeric attributes

Association rules are useful for determining correlations between attributes of a relation and have applications in the marketing, financial, and retail sectors. Furthermore, optimized association rules are an effective way to focus on the most interesting characteristics involving certain attributes. Optimized association rules are permitted to contain uninstantiated attributes and the problem is to determine instantiations such that either the support, confidence, or gain of the rule is maximized. In this paper, we generalize the optimized gain association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. Our generalized association rules enable us to extract more useful information about seasonal and local patterns involving the uninstantiated attribute. For rules containing a single numeric attribute, we present an algorithm with linear complexity for computing optimized gain rules. Furthermore, we propose a bucketing technique that can result in a significant reduction in input size by coalescing contiguous values without sacrificing optimality. We also present an approximation algorithm based on dynamic programming for two numeric attributes. Using recent results on binary space partitioning trees, we show that the approximations are within a constant factor of the optimal optimized gain rules. Our experimental results with synthetic data sets for a single numeric attribute demonstrate that our algorithm scales up linearly with the attribute's domain size as well as the number of disjunctions. In addition, we show that applying our optimized rule framework to a population survey real-life data set enables us to discover interesting underlying correlations among the attributes.     

代数次数的求解算法及其在SIMON-like算法中的应用

代数次数作为布尔函数重要的密码学指标,在密码算法的设计与分析中有着重要的应用.主要研究布尔函数代数次数的求解及其在分组密码SIMON-like算法中的应用.首先,在利用真值表求解代数正规型算法的基础上建立了基于CUDA的并行求解架构,协同利用CPU和GPU的计算资源,极大地缩短了求解代数次数的时间,在较短的时间内求解了SIMON32算法和SIMECK32算法任意轮数的代数正规型和代数次数;其次,在Cube攻击理论的基础上,根据代数次数和超多项式取值之间的关系,设计了估计代数次数的概率算法,估计了一般SIMON-like算法布尔函数的代数次数;最后,从布尔函数代数次数的角度出发,给出了SIMON-like算法在选择不同循环移位参数表现的差异性,进而给出循环移位参数的选取依据.实验结果表明,SIMON算法在原始参数下,达到最大代数次数所需的轮数最短,原始参数具有更高的安全性.     

基于图的主动数据库E-RG规则执行模型研究

本文研究主动数据库的E－RG主动规则的执行模型。E－RG主规则包含由CA规则间基本时序关系导出控制结构，是一种高层次的主动规则。它既支持CA规则的并发执行，又易于规范规则集的行为特性。E－RG主动规则的执行需要扩展的嵌套事务模型，我们已经使用一种形式框架准确，完整地刻画该事务模型。本文依据扩展的嵌套事务模型的正确性准则，给出正确实现并发的嵌套事务原子性和隔离性的锁规则，并使用一种调度算法保证主动规则E－RG中所包含的时序语义。     

A comparative analysis of cellular automata models for simulation of small urban areas in Galicia,NW Spain

Urban growth models developed in the second half of the 20th century have allowed for a better understanding of the dynamics of urban growth. Among these models, cellular automata (CA) have become particularly relevant because of their ability to reproduce complex spatial and temporal dynamics at a global scale using local and simple rules. In the last three decades, many urban CA models that proved useful in the simulation of urban growth in large cities have been implemented. This paper analyzes the ability of some of the main urban CA models to simulate growth in a study area with different characteristics from those in which these models have been commonly applied, such as slow and low urban growth. The comparison of simulation results has allowed us to analyze the strengths and weaknesses of each model and to identify the models that are best suited to the characteristics of the study area. Results suggest that models which simulate several land uses can capture better land use dynamics in the study area but need more objective and reliable calibration methods.     

Practical security against linear cryptanalysis for SMS4-like ciphers with SP round function

SMS4,a block cipher whose global structure adopts a special unbalanced Feistel scheme with SP round function,is accepted as the Chinese National Standard for securing Wireless LANs.In this paper,in order to evaluate the security against linear cryptanalysis,we examine the upper bound of the maximum linear characteristic probability of SMS4-like ciphers with SP round function.In the same way as for SPN ciphers,it is sufficient to consider the lower bound of the number of linear active s-boxes.We propose a formula to compute the lower bound of the number of linear active s-boxes with regard to the number of rounds.The security threshold of SMS4-like ciphers can be estimated easily with our result.Furthermore,if the number of input words in each round of SMS4-like cipher is m,we find that it is unnecessary for designers to make the linear branch number of P greater than 2 m with respect to linear cryptanalysis.     

A fuzzy neural network with fuzzy impact grades

Fuzzy rule derivation is often difficult and time-consuming, and requires expert knowledge. This creates a common bottleneck in fuzzy system design. In order to solve this problem, many fuzzy systems that automatically generate fuzzy rules from numerical data have been proposed. In this paper, we propose a fuzzy neural network based on mutual subsethood (MSBFNN) and its fuzzy rule identification algorithms. In our approach, fuzzy rules are described by different fuzzy sets. For each fuzzy set representing a fuzzy rule, the universe of discourse is defined as the summation of weighted membership grades of input linguistic terms that associate with the given fuzzy rule. In this manner, MSBFNN fully considers the contribution of input variables to the joint firing strength of fuzzy rules. Afterwards, the proposed fuzzy neural network quantifies the impacts of fuzzy rules on the consequent parts by fuzzy connections based on mutual subsethood. Furthermore, to enhance the knowledge representation and interpretation of the rules, a linear transformation from consequent parts to output is incorporated into MSBFNN so that higher accuracy can be achieved. In the parameter identification phase, the backpropagation algorithm is employed, and proper linear transformation is also determined dynamically. To demonstrate the capability of the MSBFNN, simulations in different areas including classification, regression and time series prediction are conducted. The proposed MSBFNN shows encouraging performance when benchmarked against other models.     

Synchronous cellular automata-based scheduler initialized by heuristic and modeled by a pseudo-linear neighborhood

Cellular automata (CA) are able to produce a global behavior from local interactions between their units. They have been applied to the task scheduling problem in multiprocessor systems in a very distinguished way. As this problem is NP-Complete, heuristics and meta-heuristics are usually employed. However, these techniques must always start the scheduling process from scratch for each new parallel application given as input. On the other hand, the main advantage to use CA for scheduling is the discovery of rules while solving one application and their subsequent reuse in other instances. Recently studies related to CA-based scheduling have shown relevant approaches as the use of synchronous updating in CA evolution and good results in multiprocessor systems with two processors. However, some aspects, such as the low performance of CA-based schedulers in architectures with more than two processors and during the reuse of the discovered rules, need to be investigated. This paper presents two new models to improve CA-based scheduling to deal with such aspects. The first proposal refers to the employment of a construction heuristic to initialize CA evolution and the second one is a new neighborhood model able to capture the dependence and relations strength among the tasks in a very simple way. It was named pseudo-linear neighborhood. An extensive experimental evaluation was performed using graphs of parallel programs found in the literature and new ones randomly generated. Experimental analysis showed the combined application of both techniques makes the search for CA transition rules during learning stage more robust and leads to a significant gain when considering the reuse of them on real-world conditions.     

一种基于局部属性集的规则确定度

在传统的粗糙集中,利用确定度来评测决策规则的确定性,然而当多个决策规则拥有相同的确定度时,对给定的对象进行分类变得困难。基于局部属性集对决策规则确定性的影响,提出一种新的规则确定度,能充分反映决策规则的确定性在局部属性集上的差异。实例表明新的确定度对决策规则有较好的评测。     

“切”与“折”的游戏——论卡片设计中切与折的应用

根据市场上充满智慧和趣味的卡片设计,研究和探索隐藏在它背后的"游戏"规则,如对纸张和印刷工艺的要求,美学和造型上的规则,所表现出的图形创意以及由平面转向空间的构成关系等。通过"以小见大"立足于一个小而精的设计载体——卡片,来讨论和研究经过切与折的设计后所反映出的新图形,新空间等的美学内涵和设计师赋予它的情趣魅力,以及它映射出的设计理念,让设计更赋细节和生活情趣,做到真正的人性化设计。     

Strategies for contextual reasoning with conflicts in ambient intelligence

Ambient Intelligence environments host various agents that collect, process, change and share the available context information. The imperfect nature of context, the open and dynamic nature of such environments and the special characteristics of ambient agents have introduced new research challenges in the study of Distributed Artificial Intelligence. This paper proposes a solution based on the Multi-Context Systems paradigm, according to which local knowledge of ambient agents is encoded in rule theories (contexts), and information flow between agents is achieved through mapping rules that associate concepts used by different contexts. To resolve potential inconsistencies that may arise from the interaction of contexts through their mappings (global conflicts), we use a preference ordering on the system contexts, which may express the confidence that an agent has in the knowledge imported by other agents. On top of this model, we have developed four alternative strategies for global conflicts resolution, which mainly differ in the type and extent of context and preference information that is used to resolve potential conflicts. The four strategies have been respectively implemented in four versions of a distributed algorithm for query evaluation and evaluated in a simulated P2P system.     

The convergence rate of the sandwich algorithm for approximating convex functions

The Sandwich algorithm approximates a convex function of one variable over an interval by evaluating the function and its derivative at a sequence of points. The connection of the obtained points is a piecewise linear upper approximation, and the tangents yield a piecewise linear lower approximation. Similarly, a planar convex figure can be approximated by convex polygons. Different versions of the Sandwich algorithm use different rules for selecting the next evaluation point. We consider four natural rules (interval bisection, slope bisection, maximum error rule, and chord rule) and show that the global approximation error withn evaluation points decreases by the order ofO(1/n ²), which is optimal. By special examples we show that the actual performance of the four rules can be very different from each other, and we report computational experiments which compare the performance of the rules for particular functions.     

An efficient sensor quantization algorithm for decentralized estimation fusion

In this paper, we consider the design problem of optimal sensor quantization rules (quantizers) and an optimal linear estimation fusion rule in bandwidth-constrained decentralized random signal estimation fusion systems. First, we derive a fixed-point-type necessary condition for both optimal sensor quantization rules and an optimal linear estimation fusion rule: a fixed point of an integral operation. Then, we can motivate an iterative Gauss–Seidel algorithm to simultaneously search for both optimal sensor quantization rules and an optimal linear estimation fusion rule without Gaussian assumptions on the joint probability density function (pdf) of the estimated parameter and observations. Moreover, we prove that the algorithm converges to a person-by-person optimal solution in the discretized scheme after a finite number of iterations. It is worth noting that the new method can be applied to vector quantization without any modification. Finally, several numerical examples demonstrate the efficiency of our method, and provide some reasonable and meaningful observations how the estimation performance is influenced by the observation noise power and numbers of sensors or quantization levels.