防火墙规则配置错误快速检测算法

在防火墙的规则配置中潜伏着一些问题：安全管理员可能在最初配置规则表的时候,出现一些错误;随着规则表中规则数目的增长,不同的规则之间发生冲突的可能性也相应增加。该文对防火墙规则配置过程中可能出现的错误进行了分析,介绍了防火墙规则配置错误的几种常见类型,给出了发现错误的算法,并根据防火墙规则表的特点对算法进行了改进,提高了规则配置错误的检测效率。     

Inferring Minimal Functional Dependencies in Horn and q-Horn Theories

In this paper, we study various problems related to the inference of minimal functional dependencies in Horn and q-Horn theories. We show that if a Horn theory is represented by a Horn CNF, then there exists an incrementally polynomial algorithm for inferring all minimal functional dependencies. On the other hand, if a Horn theory is represented as the Horn envelope of a given set of models, then there exists a polynomial total time algorithm for this inference problem if and only if there exists such an algorithm for dualizing a positive CNF. Finally, we generalize our results to the case of q-Horn theories, and show that all the considered problems can be reduced in polynomial time to the corresponding problems for Horn theories.     

On minimum-time paths of bounded curvature with position-dependent constraints

We consider the problem of a particle traveling from an initial configuration to a final configuration (given by a point in the plane along with a prescribed velocity vector) in minimum time with non-homogeneous velocity and with constraints on the minimum turning radius of the particle over multiple regions of the state space. Necessary conditions for optimality of these paths are derived to characterize the nature of optimal paths, both when the particle is inside a region and when it crosses boundaries between neighboring regions. These conditions are used to characterize families of optimal and nonoptimal paths. Among the optimality conditions, we derive a “refraction” law at the boundary of the regions that generalizes the so-called Snell’s law of refraction in optics to the case of paths with bounded curvature. Tools employed to deduce our results include recent principles of optimality for hybrid systems. A numerical example is given to demonstrate the derived results.     

Die Lösung des Anfangs-Randwertproblems für die Wärmeleitungsgleichung im ℝ3 mit einer Integralgleichungs-methode nach dem Rotheverfahrenmit einer Integralgleichungs-methode nach dem Rotheverfahren

We are looking for a solution of the initial boundary value problem for the threedimensional heat equation in a compact domain with a boundary of continous curvature. We use Rothe's line method, which works by discretisation of the time variable. For every time step there remains an elliptic boundary value problem, which is solved by means of an integral equation. The so obtained approximate solutions converge to the exact solution of the original problem. In case of a sphere we find a simple error estimate for the approximation. For two initial conditions the practical computations show, that the integral equations method yields useful results with relative small effort.     

On the reachability of a version of graph-rewriting system

In this paper, we consider a problem on the reachability of a version of graph-rewriting system. It deals with 3-regular graphs with states for the vertices. They differ from ordinary graphs so that a cyclic order of the edges is assigned on each vertex. Graphs are rewritten with a rule set of graph rewriting. For any two such connected graphs with at least four vertices of distinct states, we show that there exists a rule set that rewrites one to the other.     

一种基于十五阶的FastICA改进算法

快速独立分量分析（FastICA）因其收敛速度快而被受关注,但存在初始值选取不当可能导致算法的收敛速度减慢甚至不收敛的问题。针对基本牛顿迭代FastICA算法对初始值选择比较敏感的缺点,以最大化负熵为目标函数,引入十五阶牛顿迭代的修正形式对FastICA算法的核心迭代过程进行改进,改进算法的收敛性不再依赖于初始值的选择,而且具有更快的收敛速度。将改进算法应用到仿真实验,实验结果显示,改进算法在分离效果相当的前提下,迭代次数更少,收敛速度更快,而且收敛速度更加稳定。     

H∽ performance controller parameterisation of linear switching plants under uncontrolled switching

This paper addresses the problem of H_∽ performance controller parameterisation for a plant switching amongst a finite family of given configurations. It is assumed that switching is uncontrolled, namely governed by some arbitrary switching rule, and that the controller has the information of the current configuration. Based on Riccati inequalities, there exists a set of controller parameterisation which ensures that the closed-loop switching linear system under uncontrolled switching achieves certain H_∽ controlled performance.     

Manipulation Complexity of Same-System Runoff Elections

Do runoff elections, using the same voting rule as the initial election but just on the winning candidates, increase or decrease the complexity of manipulation? Does allowing revoting in the runoff increase or decrease the complexity relative to just having a runoff without revoting? For both weighted and unweighted voting, we show that even for election systems with simple winner problems the complexity of manipulation, manipulation with runoffs, and manipulation with revoting runoffs are independent. On the other hand, for some important, well-known election systems we determine what holds for each of these cases. For no such systems do we find runoffs lowering complexity, and for some we find that runoffs raise complexity. Ours is the first paper to show that for natural, unweighted election systems, runoffs can increase the manipulation complexity.     

Finite Difference Solutions of Incompressible Flow Problems with Corner Singularities

Two problems that include corner singularities are considered. The first concerns the flow of a viscous fluid in a channel driven by a constant pressure gradient, when the velocity satisfies a two-dimensional Poisson equation. The second is Stokes flow in a two-dimensional region when the stream-function satisfies the biharmonic equation. For both problems the boundaries of the domains contain corners. For corner angles greater than some critical value, the stress or the vorticity is singular. Using both a formal analysis and numerical results, we show that numerical approximations for the stream-function and velocity, obtained by using standard second-order finite difference methods, still converge to the exact solutions despite the corner singularities. However, the convergence rate is lower than second-order and the deterioration in the accuracy is not local, i.e., not confined to the corner. On the other hand, even though the vorticity solution of the Stokes problem does not converge, it diverges only locally. At a finite distance from the corner, the vorticity converges with the same rate as the stream-function. Adaptive methods for improving the accuracy are also discussed.     

快速的三维人手运动跟踪方法研究

三维人手运动跟踪是人机交互领域的一个重要研究方向.提出了一种新的基于模型的三维人手运动跟踪方法,该方法将层次优化嵌入到基于粒子滤波器的跟踪框架中,通过在隐状态空间中对粒子采样来提高粒子滤波器采样效率.首先,提出了采用低维隐状态来描述人手的配置状态,并根据人手的生理运动约束建立人手动态模型;其次,为提高粒子在隐状态空间的采样效率,提出了采用层次遗传优化来快速地在局部寻找好的粒子,并以此作为重要度采样函数修正粒子滤波的采样算法.实验结果表明,该方法可以在人手自遮挡存在时的复杂背景下快速地对人手运动进行跟踪.     

Real-time reversible iterative arrays

Iterative arrays are one-dimensional arrays of interconnected interacting finite automata. The cell at the origin is equipped with a one-way read-only input tape. We investigate iterative arrays as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. It is shown that real-time reversible iterative arrays can simulate restricted variants of stacks and queues. It turns out that real-time reversible iterative arrays are strictly weaker than real-time reversible cellular automata. On the other hand, a non-semilinear language is accepted. We show that real-time reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts with the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the non-semidecidability of several other properties. Several closure properties are also derived.     

CA与生命游戏演化的组合模型*

基于摩尔奇偶型CA,提出一种结合生命游戏的演化模型.首先设置初始构型进行摩尔奇偶型规则演化,再引入生命游戏规则,按游戏规则演化;最后依此重复摩尔奇偶规则和生命游戏规则,直到演化整个元胞空间.证实在摩尔奇偶型CA的基础上,结合生命游戏在很大程度上减小了演化过程对初始构型的依赖,出现更为丰富的图元以及基于图元和演化框架的动态图案,且演化过程仍然符合摩尔奇偶型CA的演化规律.结合模型可以避免演化过度依赖初始构型以及演化过程的单调性,而且组合演化模型可以应用于图案生成,生成保持风格的规则几何纹理图案,丰富图案的生成方法.     

What is decidable about partially observable Markov decision processes with ω-regular objectives

We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples.     

多动态目标的多机器人协同环航控制

主要研究了多个非完整机器人对多个动态目标的协同环航控制问题;首先,针对多目标护航任务,建立目标扩展圆形构型,以期完成紧密目标保卫任务;其次,针对护航机器人,通过利用自身及相邻节点的位置与方位信息及所包围的动态目标的中心位置及扩展半径设计分布式时变圆形编队控制协议,实现预定几何分布下的机器人环航编队设计;其中,通过引入虚拟信号变量设计期望的速度及角速度控制律,利用反步技术提出了一种新的考虑时变护航半径的分布式控制策略;在对目标节点速度的温和假设下,所提出的编队控制器可以驱动多护航机器人渐近收敛到以多目标中心的圆上,同时维持一个预定的几何编队配置;Lyapunov分析证明了所有的误差都可以渐进稳定到原点,数值仿真核实了所构建的控制方案的可行性。     

3D crystal structure identification using fuzzy neural networks

The problem of recognizing nano-scale images of lattice projections comes down to identification of crystal lattice structure. The paper considers two types of fuzzy neural networks that can be used for tackling the problem at hand: the Takagi-Sugeno-Kang model and Mamdani-Zadeh model (the latter being a modification of the Wang-Mendel fuzzy neural network). We offer a threestage neural network learning process. In the first two stages crystal lattices are grouped in non-overlapping classes, and lattices belonging to overlapping classes are recognized at the third stage. In the research, we thoroughly investigate the applicability of the neural net models to structure identification of 3D crystal lattices.     

Multi-adjoint concept lattices with heterogeneous conjunctors and hedges

This paper is related, on the one hand, to the framework of multi-adjoint concept lattices with heterogeneous conjunctors and, on the other hand, to the use of intensifying hedges as truth-stressers. Specifically, we continue on the line of recent works by Belohlavek and Vychodil, which use intensifying hedges as a tool to reduce the size of a concept lattice. In this paper we use hedges as a reduction tool in the general framework of multi-adjoint concept lattices with heterogeneous conjunctors.     

改进的限定Voronoi图梯形检测带细分算法

针对已有的限定Voronoi图生成算法在一些复杂约束条件下不能收敛的问题,通过引入控制因子,给出一种 改进的限定Voronoi图梯形检测带细分算法。在计算初始Voronoi生长元的过程中,引入外部和内部限定线段端点 保护圆半径控制因子,控制限定线段两端点附近的Voronoi边的尺寸;在细分梯形检测带的过程中,引入外部和内部 限定线段尺寸控制因子,控制位于限定线段上的Voronoi边的尺寸。实验结果表明,本算法对于内部边界约束、线束 约束条件以及不规则区域均可以得到质量较好、满足约束条件的限定Voronoi图。     

Stochastic Cellular Automata Solutions to the Density Classification Problem

In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA. We investigate how randomness in CA may help us solve the problem. We analyse the behaviour of stochastic CA rules that perform the density classification task. We show that describing stochastic rules as a “blend” of deterministic rules allows us to derive quantitative results on the classification time and the classification time of previously studied rules. We introduce a new rule whose effect is to spread defects and to wash them out. This stochastic rule solves the problem with an arbitrary precision, that is, its quality of classification can be made arbitrarily high, though at the price of an increase of the convergence time. We experimentally demonstrate that this rule exhibits good scaling properties and that it attains qualities of classification never reached so far.     

Membership function modification of fuzzy logic controllers withhistogram equalization

In most fuzzy logic controllers (FLCs), initial membership functions (MFs) are normally laid evenly all across the universes of discourse (UD) that represent fuzzy control inputs. However, for evenly distributed MFs, there exists a potential problem that may adversely affect the control performance; that is, if the actual inputs are not equally distributed, but instead concentrate within a certain interval that is only part of the entire input area, this will result in two negative effects. On one hand, the MFs staying in the dense-input area will not be sufficient to react precisely to the inputs, because these inputs are too close to each other compared to the MFs in this area. The same fuzzy control output could be triggered for several different inputs. On the other hand, some of the MFs assigned for the sparse-input area are "wasted". In this paper we argue that, if we arrange the placement of these MFs according to a statistical study of feedback errors in a closed-loop system, we can expect a better control performance. To this end, we introduce a new mechanism to modify the evenly distributed MFs with the help of a technique termed histogram equalization. The histogram of the errors is actually the spatial distribution of real-time errors of the control system. To illustrate the proposed MF modification approach, a computer simulation of a simple system that has a known mathematical model is first analyzed, leading to our understanding of how this histogram-based modification mechanism functions. We then apply this method to an experimental laser tracking system to demonstrate that in real-world applications, a better control performance can he obtained by using this proposed technique.