Correctness of Algebraic Extensions of Models of Classification Algorithms

The binary representation of each classification from a subset of a space of admissible classifications is considered. A metric in a unit cube is introduced, and a correct algebra of classification algorithms is constructed. The correctness and completeness of a model of classification algorithms are proved. An example of construction of a complete model for a classification problem is considered.     

Stability properties of equilibria of classes of cooperativesystems

This note deals with the constant control problem for homogeneous cooperative and irreducible systems. These systems serve as models for positive systems. A necessary and sufficient condition for global asymptotic stability of the zero solution of this class of systems is known. Adding a constant control allows to shift the equilibrium point from zero to a point in the first orthant. We prove that for every nontrivial nonnegative control vector a unique nontrivial equilibrium point is achieved which is globally asymptotically stable if the zero solution of the uncontrolled system is globally asymptotically stable. In addition a converse result is provided. Finally a stability result for a particular class of Kolmogorov systems is established. We compare our main results to those in the literature     

Systems of generators for ideals of algebra of convergent differential series

Differential algebra of convergent power series that depend on an arbitrary finite number of variables is considered. The concept of a passive family of generators is defined for a differential ideal of this algebra. It is a further extension of the concept of the Groebner basis. The theorem that allows checking whether a family of generators is passive and ensures that the point solution of an infinite system of equations exists and is unique in this algebra is proved.     

Solution of problem of identification of time shift of pseudorandom sequences on the basis of nonlinear probabilistic criteria

A solution of the problem of identification of the time shift of pseudorandom sequences received against a background of interference is proposed. The solution is based on a nonlinear probabilistic criterion—the criterion of minimum a posteriori integral estimation error. An algorithm of nonlinear parametric identification that yields a solution of the problem is synthesized. A numerical example of the identification of the time shift of a concrete sequence that confirms the effectiveness and adequate degree of efficiency of the algorithm proposed in the study is presented.     

基于语义事务分解的可串行性

数据库应用中长事务的出现严重降低了系统的性能，一些研究者为解决这一问题提出了利用事务的语义信息对事务进行分解的方法，但所得结论仍然存在缺陷．本文从用户定义的后续集出发给出了正确步进串行历史的概念，可以很容易证明正确步进串行历史是用户可接受的正确历史，并以此作为判定一个历史是否正确的基础．重后，证明了当用户给出的后续集满足约束2时，优化前驱图的无环性是判定一个正确历史的充要条件．     

The stabilization of digraphs of variable parameter systems

Directed acyclic graphs of dynamical systems are considered. Such graphs possess a natural and unique layering of their nodes. Each node is taken to be associated with a dynamical system in such a way that each parameter of a given system is some nonlinear function of the states of systems connected to it and lying in higher layers of the network. Such an arrangement we call a digraph of variable parameter systems. It is shown that digraphs of a large class of variable parameter systems may be stabilized by associating a compensator (of observer-linear feedback type) with each variable parameter system. Each compensator need only observe the output and input of the variable parameter system with which it is associated; however, an argument is presented to show that the performance of the controlled digraph is enhanced if the compensators signal to each other in a manner consistent with the flow of the parametric disturbances through the network. In this sense, it is shown that a network of variable parameter systems is efficiently stabilized by a multilevel, or hierarchical, control system.     

Organization of the non-uniqueness of a canonical structure of linear multivariable systems

This paper is concerned with organizing the non-uniqueness of the canonical structure of a class of linear time-invariant multivariable systems in such a way as to provide an efficient tool in control system design. A phase-variable block form of state equations is used to describe the system class in the transformed coordinates. The transformation procedure is characterized by an arbitrary parameter (in the form of a submatrix) which adds an attractive degree of freedom in the solution of practical problems. As a demonstration, the procedure is applied to synthesize a minimum-time deadbeat controller for linear discrete-time systems. A family of controllers, not identifiable by earlier approaches, is developed and that controller which additionally minimizes a control energy criterion is determined. A numerical example is provided to illustrate the different aspects of this work.     

无线投影机网关系统设计

无线投影机网关是投影机的附属设备,在PC与投影机之间建立无线连接,将PC的屏幕图像传输到投影机上,从而使PC摆脱与投影机之间的连线束缚.该网关设备在设计中采用的GX533是AMD的一款嵌入式x86处理器,GX533在机顶盒、网络终端、瘦客户机、廉价电脑等领域有着广泛的应用.分析了GX533处理器及其南桥控制器的结构原理,在此基础上介绍无线投影机网关的系统设计.     

Complexity of approximation of 3-edge-coloring of graphs

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. To make the gap more precise, we study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We show that it is an NP-hard problem to approximate such invariants with an error O(n1−ε), where n denotes the order of the graph and 0<ε<1 is a constant.     

Online version of the theorem of Thue

A sequence S is nonrepetitive if no two adjacent blocks of S are the same. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over 3 symbols. We consider the online variant of this result in which a nonrepetitive sequence is constructed during a play between two players: Bob is choosing a position in a sequence and Alice is inserting a symbol on that position taken from a fixed set A. The goal of Bob is to force Alice to create a repetition, and if he succeeds, then the game stops. The goal of Alice is naturally to avoid that and thereby to construct a nonrepetitive sequence of any given length.We prove that Alice has a strategy to play arbitrarily long provided the size of the set A is at least 12. This is the online version of the theorem of Thue. The proof is based on nonrepetitive colorings of outerplanar graphs. On the other hand, one can prove that even over 4 symbols Alice has no chance to play for too long. The minimum size of the set of symbols needed for the online version of Thue?s theorem remains unknown.     

Submodular Functions in Problems of Synthesis of Networks

It is established that any problem of minimization of a general submodular function is the problem of determination of a minimum cut in a network if, for an arbitrary set, the dual function is defined as the sum of its values on the two-element subsets of this set. This result is used to synthesize a network with the help of a cut submodular function.     

Formalized analysis of structural characteristics of large complexsystems

Macrostructural modelization is paramount to the development of large complex systems (LCS). The paper explores the macrostructural modelization of LCS in terms of a block diagram based model and a grammar based model. Firstly, the macrostructural modelization problem of LCS is formulated. Secondly, a block diagram based model is proposed and established for LCS. Specifically, two general-purpose information-processing modules are proposed and constructed, called perception cube and decision spheroid. Thirdly, a grammar based model is proposed and established for LCS through applying formal language theory to the block diagram based model. Specifically, perception cube and decision spheroid are visually represented as context-free grammars, named fusion grammar and synthesis grammar, respectively. Through a stratified constructive linkup between a stream of bottom-up growing fusion grammars and a stream of top-down growing synthesis grammars, a level of LCS is constructively defined and accordingly represented as a context-free grammar, named level grammar. Then, a whole LCS is represented as a context-free grammar through a compounding of all level grammars. Finally, a case study is presented to demonstrate the potential usability of the proposed and established models of LCS     

The boundedness of all products of a pair of matrices is undecidable

We show that the boundedness of the set of all products of a given pair Σ of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ρ(Σ) is not computable because testing whether ρ(Σ)1 is an undecidable problem. As a consequence, the robust stability of linear systems under time-varying perturbations is undecidable, and the same is true for the stability of a simple class of hybrid systems. We also discuss some connections with the so-called “finiteness conjecture”. Our results are based on a simple reduction from the emptiness problem for probabilistic finite automata, which is known to be undecidable.     

Application of microprocessor networks for the solution of diffusion equation

The availibility of low cost microprocessors, memories and ancilliary circuits has made the construction of large networks of such devices feasible where each microcomputer is dedicated to a specific task. The parallel computation of the diffusion equation is a particular application of such a multi-microcomputer network where each microcomputer simulates a given region and exchanges partial results with its neighbours. Structure of a network where each node consists of a microcomputer linked to other nodes by means of serial communication lines is described. The explicit finite difference algorithm is adapted for an 8-bit architecture most commonly available today. The algorithm is emulated on a minicomputer and the results presented. Availibility of processing power and memory at each node is significant for the simulation of non-linear problems which has been discussed. The significance of full parallelism where a microcomputer is allocated to each problem node and partial parallelism where a microcomputer simulates a number of nodes which form a region is covered.     

基于散乱点的任意拓扑曲面建模及绘制研究

对曲面建模进行了研究,提出了一种基于散乱点的曲面重建方法.给出三维空间的散乱点,采用3个步骤重构出三角化曲面:首先按近似共面程度对点集聚类,把接近共面的点归为同一类,然后根据空间点的邻接关系进行局部调整,最后对点集和点集之间的区域进行三角割分,得到三角化曲面,所得曲面用OpenGL进行绘制.     

Parametrization of the Regular Equivalences of the Canonical Controller

We study control problems for linear systems in the behavioral framework. Our focus is a class of regular controllers that are equivalent to the canonical controller. The canonical controller is a particular controller that is guaranteed to solve the control problem whenever a solution exists. However, it has been shown that, in most cases, the canonical controller is not regular. The main result of the note is a parametrization of all regular controllers that are equivalent to the canonical controller. The parametrization is then used to solve two control problems. The first problem is related to designing a regular controller that uses as few control variables as possible. The second problem is to design a regular controller that satisfies a predefined input-output partitioning constraint. In both problems, based on the parametrization, we present algorithms for designing the controllers.     

Palindromic complexity of codings of rotations

We study the palindromic complexity of infinite words obtained by coding rotations on partitions of the unit circle by inspecting the return words. The main result is that every coding of rotations on two intervals is full, that is, it realizes the maximal palindromic complexity. As a byproduct, a slight improvement about return words in codings of rotations is obtained: every factor of a coding of rotations on two intervals has at most 4 complete return words, where the bound is realized only for a finite number of factors. We also provide a combinatorial proof for the special case of complementary-symmetric Rote sequences by considering both palindromes and antipalindromes occurring in it.     

Symmetricity of the solution of semidefinite programming

Symmetricity of an optimal solution of Semi-Definite Programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.     

Scale-based detection of corners of planar curves

A technique for detecting and localizing corners of planar curves is proposed. The technique is based on Gaussian scale space, which consists of the maxima of absolute curvature of the boundary function presented at all scales. The scale space of isolated simple and double corners is first analyzed to investigate the behavior of scale space due to smoothing and interactions between two adjacent corners. The analysis shows that the resulting scale space contains line patterns that either persist, terminate, or merge with a neighboring line. Next, the scale space is transformed into a tree that provides simple but concise representation of corners at multiple scales. Finally, a multiple-scale corner detection scheme is developed using a coarse-to-fine tree parsing technique. The parsing scheme is based on a stability criterion that states that the presence of a corner must concur with a curvature maximum observable at a majority of scales. Experiments were performed to show that the scale space corner detector is reliable for objects with multiple-size features and noisy boundaries and compares favorably with other corner detectors tested     

AMBA ASB总线系统主设备的设计

IC设计已经进入系统芯片（system on a chip，Soc）时代。片上总线作为SoC集成系统的互连结构，可以解决各个IP功能模块间的相互通信问题。AMBA总线由于其高性能和ARM处理器的广泛应用以及该总线协议的完全开放性，逐渐成为事实上的SoC总线标准。对现有的微处理器IP核按照AMBA ASB片上总线的协议进行改造，使其能够作为主设备方便的集成在SoC系统中，并使用FPGA验证了基于AMBA总线的系统集成的正确性。