Unary finite automata vs. arithmetic progressions

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.     

Parameterized solution to a class of sylvester matrix equations

A class of formulas for converting linear matrix mappings into conventional linear mappings are presented. Using them, an easily computable numerical method for complete parameterized solutions of the Sylvester matrix equation AX-EXF=BY and its dual equation XA-FXE=YC are provided. It is also shown that the results obtained can be used easily for observer design. The method proposed in this paper is universally applicable to linear matrix equations.     

加权范数下矩阵方程组的对称解及其最佳逼近

应用复合最速下降法,给出了求解矩阵方程组[(AXB=E,CXD=F)]加权范数下对称解及最佳逼近问题的迭代解法。对任意给定的初始矩阵,该迭代算法能够在有限步迭代计算之后得到矩阵方程组的对称解,并且在上述解集合中也可给出指定矩阵的最佳逼近矩阵。     

On norm bounds for algebraic Riccati and Lyapunov equations

New lower bounds on the spectral norms of the positive definite solutions to the continuos and discrete algebraic matrix Riccati and Lyapunov equations are derived. These bounds are much easier to compute than previously available bounds and appear to be considerably tighter in many cases.     

Solving linear differential equations as a minimum norm least squares problem with error-bounds

Linear ordinary/partial differential equations (DEs) with linear boundary conditions (BCs) are posed as an error minimization problem. This problem has a linear objective function and a system of linear algebraic (constraint) equations and inequalities derived using both the forward and the backward Taylor series expansion. The DEs along with the BCs are approximated as linear equations/inequalities in terms of the dependent variables and their derivatives so that the total error due to discretization and truncation is minimized. The total error along with the rounding errors render the equations and inequalities inconsistent to an extent or, equivalently, near-consistent, in general. The degree of consistency will be reasonably high provided the errors are not dominant. When this happens and when the equations/inequalities are compatible with the DEs, the minimum value of the total discretization and truncation errors is taken as zero. This is because of the fact that these errors could be negative as well as positive with equal probability due to the use of both the backward and forward series. The inequalities are written as equations since the minimum value of the error (implying error-bound and written/expressed in terms of a nonnegative quantity) in each equation will be zero. The minimum norm least-squares solution (that always exists) of the resulting over-determined system will provide the required solution whenever the system has a reasonably high degree of consistency. A lower error-bound and an upper error-bound of the solution are also included to logically justify the quality/validity of the solution.     

Dynamic equations in descriptor form

This paper studies a general form of sets of equations that is often the product of problem formulation in large-scale systems, especially when the equations are expressed in terms of the natural describing variables of the system. Such equations represent a broad class of time-evolutionary phenomena, and include as special cases ordinary static equations of arbitrary dimension, ordinary state-space equations, combinations of static and dynamic equations, and noncausal systems. The main thrust of the paper is to show (for sets of linear equations) that familiar concepts of dynamic system theory can be extended to this more general class, although sometimes with significant modification. Two new (and essentially dual) concepts, that of solvable and conditionable sets of equations, are found to be fundamental to the study of equations of this form. The notion of initial conditions, although not directly related to a state, is used as a general solution method for equations of this type. In addition a set of necessary and sufficient conditions for a set of dynamic equations to contain an embedded state-space representation is derived.     

Elimination of overflow oscillations in direct form digital filters using saturation arithmetic

A novel frequency-domain criterion for the elimination of limit cycles in a class of digital filters using saturation arithmetic is presented. An example showing the effectiveness of the present criterion is given.     

Iterative methods for systems of equations with interval coefficients and linear form

We introduce iterative methods for systems of equations with interval coefficients and linear form by suitable matrix splittings. When compared to the iterative methods for systems amenable to iteration introduced in [1], improved convergence and inclusion properties can be proved under suitable conditions. The method can also be used in the solution of specific nonlinear systems of equations by interval arithmetic methods.     

Equivalence of minimal time and minimal norm control problems for semilinear heat equations

In this paper, we establish the equivalence of minimal time and minimal norm control problems for semilinear heat equations in which the controls are distributed internally in an open subset of the state domain. As an application, the Bang–Bang property for minimal norm controls are also presented.     

Iterative algorithm for minimal norm least squares solution to general linear matrix equations

This paper is concerned with minimal norm least squares solution to general linear matrix equations including the well-known Lyapunov matrix equation and Sylvester matrix equation as special cases. Two iterative algorithms are proposed to solve this problem. The first method is based on the gradient search principle for solving optimization problem and the second one can be regarded as its dual form. For both algorithms, necessary and sufficient conditions guaranteeing the convergence of the algorithms are presented. The optimal step sizes such that the convergence rates of the algorithms are maximized are established in terms of the singular values of some coefficient matrix. It is believed that the proposed methods can perform important functions in many analysis and design problems in systems theory.     

微机与一种主动发送式智能仪表的通信算法

为了解决工业控制中微机与仪表的通信问题，以冰箱环境模拟试验室温度监控系统为背景，给出了一种通过RS232方式、利用VB的MSComm控件实现的微机与主动发送式智能仪表的通信算法，并详细叙述了该算法所需的数据结构和数据采集及处理的具体流程。该算法已在实践中得到广泛应用。     

Interpolation with multiple norm constraints

This paper considers the problem of finding matrix-valued rational functions that satisfy two-sided residue interpolation conditions subject to norm constraints on their components. It is shown that this problem can be reduced to a finite-dimensional convex optimization problem. As an application, we show that under suitable assumptions on the plant, multiple objective ?₂ and ?_∞ control problems admit finite-dimensional optimal solutions and that such solutions can be computed using finite-dimensional convex programs.     

Numerical solution of a fuzzy system of linear equations with polynomial parametric form

A systems of linear equations are used in many fields of science and industry, such as control theory and image processing, and solving a fuzzy linear system of equations is now a necessity. In this work we try to solve a fuzzy system of linear equations having fuzzy coefficients and crisp variables using a polynomial parametric form of fuzzy numbers.     

一种处理障碍约束的聚类算法

根据障碍约束空间聚类问题的特点,利用图论的相关知识,提出了一种分阶段的基于图的聚类的算法。首先,通过最小生成树聚类算法,在不考虑障碍约束的情况下对空间对象进行聚类;然后,引入障碍物对上一步的聚类结果进行分割;最后,根据被障碍物分割后形成的各个类之间的障碍距离,将距离较近的两个类合并,形成最终的聚类结果。最后通过实验验证了算法的效果,而且输入参数少,时间复杂度低。     

A proof of controllability of Jordan form state equations

A proof of controllability of Jordan form state equations is presented in this paper. The proof is purely algebraic and is applicable to continuous as well as discrete state equations     

On the minimality of the Jordan form state equations

This paper proves the theorem that permits calculation of the order of the minimal realization of a system described by the Jordan form state equations. The proof is purely algebraic and is applicable both to continuous and discrete dynamic systems. The application of the theorem is illustrated by a computational example.     

The Parameterized Approximability of TSP with Deadlines

Modern algorithm theory includes numerous techniques to attack hard problems, such as approximation algorithms on the one hand and parameterized complexity on the other hand. However, it is still uncommon to use these two techniques simultaneously, which is unfortunate, as there are natural problems that cannot be solved using either technique alone, but rather well if we combine them. The problem to be studied here is not only natural, but also practical: Consider TSP, generalized as follows. We impose deadlines on some of the vertices, effectively constraining them to be visited prior to a given point of time. The resulting problem DlTSP (a special case of the well-known TSP with time windows) inherits its hardness from classical TSP, which is both well known from practice and renowned to be one of the hardest problems with respect to approximability: Within polynomial time, not even a polynomial approximation ratio (let alone a constant one) can be achieved (unless P = NP). We will show that DlTSP is even harder than classical TSP in the following sense. Classical TSP, despite its hardness, admits good approximation algorithms if restricted to metric (or near-metric) inputs. Not so DlTSP (and hence, neither TSP with time windows): We will prove that even for metric inputs, no constant approximation ratio can ever be achieved (unless P = NP). This is where parameterization becomes crucial: By combining methods from the field of approximation algorithms with ideas from the theory of parameterized complexity, we apply the concept of parameterized approximation. Thereby, we obtain a 2.5-approximation algorithm for DlTSP with a running time of k! · poly(|G|), where k denotes the number of deadlines. Furthermore, we prove that there is no fpt-algorithm with an approximation guarantee of 2-ε for any ε > 0, unless P = NP. Finally, we show that, unlike TSP, DlTSP becomes much harder when relaxing the triangle inequality. More precisely, for an arbitrary small violation of the triangle inequality, DlTSP does not admit an fpt-algorithm with approximation guarantee ((1-ε)/2)|V| for any ε > 0, unless P = NP.     

Networks of Processes with Parameterized State Space

In general, the verification of parameterized networks is undecidable. In recent years there has been a lot of research to identify subclasses of parameterized systems for which certain properties are decidable. Some of the results are based on finite abstractions of the parameterized system in order to use model-checking techniques to establish those properties. In a previous paper we presented a method which allows to compute abstractions of a parameterized system modeled in the decidable logic WS1S. These WS1S systems provide an intuitive way to describe parameterized systems of finite state processes. In practice however, the processes in the network themselves are infinite because of unbounded data structures. One source of unboundedness can be the usage of a parameterized data structure. Another typical source may be the presence of structures ranging over subsets of participating processes. E.g., this is the case for group membership or distributed shared memory consistency protocols. In this paper we use deductive methods to deal with such networks where the data structure is parameterized by the number of processes and an extra parameter. We show how to derive an abstract WS1S system which can be subject to algorithmic verification. For illustration of the method we verify the correctness of a distributed shared memory consistency protocol using PVS for the deductive verification part and the tools PAX and SMV for the algorithmic part.