On the control of max-plus linear system subject to state restriction

This paper deals with the control of discrete event systems subject to synchronization and time delay phenomena, which can be described by using the max-plus algebra. The objective is to design a feedback controller to guarantee that the system evolves without violating time restrictions imposed on the state. To this end an equation is derived, which involves the system, the feedback and the restriction matrices. Conditions concerning the existence of a feedback are discussed and sufficient conditions that ensure the computation of a causal feedback are presented. To illustrate the results of this paper, a workshop control problem is presented.     

A constructive approach to minimal realization problem of 2D systems

Unlike in the 1D case, it is not always possible to find a minimal state-space realization for a 2D system except for some particular categories. The purpose of this paper is to explore a constructive approach to the minimal Roesser model realization problem for a class of 2D systems which does not belong to the clarified categories. As one of the main results, a constructive realization procedure is first proposed. Based on the proposed procedure, sufficient conditions and explicit construction for minimal realizations of the considered 2D systems are shown. In addition, possible variations and applications of the obtained results are discussed and illustrative examples are presented.     

Balancing related methods for minimal realization of periodic systems

We propose balancing related numerically reliable methods to compute minimal realizations of linear periodic systems with time-varying dimensions. The first method belongs to the family of square-root methods with guaranteed enhanced computational accuracy and can be used to compute balanced minimal order realizations. An alternative balancing-free square-root method has the advantage of a potentially better numerical accuracy in case of poorly scaled original systems. The key numerical computation in both methods is the solution of nonnegative periodic Lyapunov equations directly for the Cholesky factors of the solutions. For this purpose, a numerically reliable computational algorithm is proposed to solve nonnegative periodic Lyapunov equations with time-varying dimensions.     

Dynamic processor allocation in scalable multiprocessors using boolean algebra *

In this paper, we study a new model for dynamic processor allocation in k-ary n-dimensional mesh or torus multiprocessors. The model uses Boolean functions to represent free processors and allocates processors by applying Boolean operations on the functions. The processor allocation algorithms based on the Boolean model can be implemented easily using binary decision diagrams(BDDs)and related software packages. To enhance the efficiency of the allocation algorithms, a reordering procedure will be introduced to change the ordering of Boolean variables in the BDD representation and thereby change the free subcube composition. Such a change leads to an improved free processor recognition capability. Complexities of the proposed allocation algorithms will be analyzed. Performance of the algorithms will be evaluated using simulation and compared with other approaches.     

On finite dimensional realization theory of discrete time nonlinear systems

We characterize finite dimensional realizability of discrete time nonlinear systems which have a Volterra series development with separable structure of the Volterra kernels.     

On parametrizations for the minimal partial realization problem

The paper considers parametrizations for minimal partial realizations of a finite sequence of Markov parameters. First it is shown that all minimal partial realizations have the same set of input and output Kronecker indices. A parametrization is obtained formulated in terms of a minimal set of extension entries. Then an I/O canonical form is used as a parametrization for the set of minimal partial realizations. It is shown that this allows to define the invariants of the problem. Moreover, the I/O canonical form is shown to contain a set of parameters that can be chosen such that any minimal partial realization can be represented.     

极小-极大-加系统(F,G,H)的能达能观性

在数字电路中,两个时间信号通过逻辑电路的"与"门相当于极大运算,"或"门相当于极小运算.因此,极小-极大-加系统可用于数字电路的时间分析.对于非线性极强的极小-极大-加系统(F,G,H),引入了分别能达和上限能观的概念.利用图论的方法给出了极小-极大-加系统(F,G,H)的状态变量xt为分别能达分量的充要条件,同时,还得到了xt为上限能观分量的充要条件.     

The generic dimension of a minimal realization of an AR System

In this paper, graph theoretical methods are developed for the determination of the generic dimension of a minimal realization of an AR system using only the structure present in the AR equations.     

A new algorithm for the minimal balanced realization of a transfer function matrix

A new algorithm is proposed here to obtain a minimal balanced realization directly from the transfer function matrix (TFM). This method which employs the singular-value decomposition (SVD) of an infinite block-Hankel matrix requires neither an initial minimal realization nor the solution of a Lyapunov matrix equation. The formulation is solely in terms of the coefficients of the transfer function matrix.     

On minimality in the partial realization problem

A compression algorithm is constructed which allows one to reduce an arbitrary realization of a finite sequence of matrices M₁,…, M_r to a minimal partial realization of M₁,…, M_r. Furthermore, a state space criterion of minimality of a partial realization and a formula for the minimal state space dimension are obtained.     

Bounds on the size of minimal nonnegative realizations for discrete-time LTI systems

Nonnegative linear time-invariant (LTI) state-space models are characterized by the property that their state variables and outputs remain nonnegative whenever the initial state and the inputs are nonnegative. Necessary and sufficient conditions for the existence of a nonnegative state-space realization of a given discrete-time (DT) impulse response were obtained recently. In this letter, we look at minimal nonnegative realizations of DT impulse responses and develop bounds on the number of state variables that are necessary.     

On optimal and reasonable control in the presence of adversaries

This paper constitutes a sketch of a unified framework for posing and solving problems of optimal control in the presence of uncontrolled disturbances. After laying down the general framework we look closely at a concrete instance where the controller is a scheduler and the disturbances are related to uncertainties in task durations.     

Linear Periodic Systems Over Dioids

A specification of the linear system theory over dioids is proposed for periodic systems. Using the conventional periodic system theory as a guideline, we study periodic systems for which the underlying algebraic structure is a dioid. The focus is on representations (impulse response and state model) associated with such systems, the properties of these representations as well as the state space realization.     

On the realization problem for stationary,homogeneous, discrete-time systems

For degree 2, stationary, homogeneous systems, we consider realizations in the form of state-affine difference equations, and in the form of feedback-free interconnections of stationary linear systems, adders, and multipliers. Realizability conditions are presented in terms of the symmetric transfer function (or kernel), and in terms of a new representation called the regular transfer function (or kernel). A procedure is given for constructing a minimal dimension state-affine realization, and the corresponding interconnection.     

On the existence of a positive realization

The positive realization problem for linear systems is to find conditions, for a given transfer function with nonnegative impulse response, to have a realization such that the resulting system is a positive system. Recently, it has been shown that, under a mild assumption on the long-term behaviour of the impulse response, this problem is related to the maximum modulus poles only. In this paper necessary and sufficient conditions for positive realizability of discrete-time systems are given. They show that also nondominant poles play a role in the most general case. Positive realizability conditions for the continuous-time case are also given.     

On the algebra of structured specifications

We develop module algebra for structured specifications with model oriented denotations. Our work extends the existing theory with specification building operators for non-protecting importation modes and with new algebraic rules (most notably for initial semantics) and upgrades the pushout-style semantics of parameterized modules to capture the (possible) sharing between the body of the parameterized modules and the instances of the parameters. We specify a set of sufficient abstract conditions, smoothly satisfied in the actual situations, and prove the isomorphism between the parallel and the serial instantiation of multiple parameters. Our module algebra development is done at the level of abstract institutions, which means that our results are very general and directly applicable to a wide variety of specification and programming formalisms that are rigorously based upon some logical system.     

The balance problem of min–max systems is co-NP hard

Min–max systems are timed discrete event dynamic systems containing min, max and plus operations. A min–max system is balanced if it admits a global cycle time (generalized eigenvalue) for every possible assignment of parameters. This paper proves that the testing of the balance property for min–max systems is co-NP hard by showing that the test of inseparability is co-NP hard. The latter result is established on a new complexity result, namely, that the testing of existence of non-trivial fixed points for monotone Boolean functions is NP-complete.     

An algorithm for identifying symmetric variables in the canonical OR-coincidence algebra system

To simplify the process for identifying 12 types of symmetric variables in the canonical OR-coincidence （COC） algebra system, we propose a new symmetry detection algorithm based on OR-NXOR expansion. By analyzing the relationships between the coefficient matrices of sub-functions and the order coefficient subset matrices based on OR-NXOR expansion around two arbitrary logical variables, the constraint conditions of the order coefficient subset matrices are revealed for 12 types of symmetric variables. Based on the proposed constraints, the algorithm is realized by judging the order characteristic square value matrices. The proposed method avoids the transformation process from OR-NXOR expansion to AND-OR-NOT expansion, or to AND-XOR expansion, and solves the problem of completeness in the dj-map method. The application results show that, compared with traditional methods, the new algorithm is an optimal detection method in terms of applicability of the number of logical variables, detection type, and complexity of the identification process. The algorithm has been implemented in C language and tested on MCNC91 benchmarks. Experimental results show that the proposed algorithm is convenient and efficient.