Fixed zeros in the model matching problem for systems over semirings

This paper studies “fixed zeros” of solutions to the model matching problem for systems over semirings. Such systems have been used to model queueing systems, communication networks, and manufacturing systems. The main contribution of this paper is the discovery of two fixed zero structures, which possess a connection with the extended zero semimodules of solutions to the model matching problem. Intuitively, the fixed zeros provides an essential component that is obtained from the solutions to the model matching problem. For discrete event dynamic systems modeled in max-plus algebra, a common Petri net component constructed from the solutions to the model matching problem can be discovered from the fixed zero structure.     

A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)

We propose an algorithm for finding the so-called principal solution of the Sylvester matrix equation over max-plus algebra. The derivation of our algorithm is based on the concept of tropical tensor product introduced by Butkovi? and Fiedler. Our algorithm reduces the computational cost of finding the principal solution from quartic to cubic. It also reduces the space complexity from quartic to quadratic. Since matrix–matrix multiplication is the most important ingredient of our proposed technique, we show how to use column-oriented matrix multiplications in order to speed-up MATLAB implementation of our algorithm. Finally, we illustrate our results and discuss the connection with the residuation theory.     

极大加可约矩阵的谱与周期时间向量的关系

提出了极大加代数上可约矩阵特征值的缺失值及冗余值的概念,得到了相应的定理;对特征值与周期时间向量分量之间的关系作了深入的研究.     

Divergent Type Quasilinear Dirichlet Problem with Singularities

A quasilinear equation of divergent type with singular data and singular coefficients is approximated by a net of equations of the same type with enough regular coefficients and data. Solutions of the net of equations are obtained by the classical methods. Known a priory estimates are improved so that a net of solutions can be considered as a solution in an appropriate algebra of generalized functions.     

Output feedback stabilization for a class of nonlinear time-evolution systems

A variety of problems in nonlinear time-evolution systems such as communication networks, computer networks, manufacturing, traffic management, etc., can be modelled as min–max-plus systems in which operations of min, max and addition appear simultaneously. Systems with only maximum (or minimum) constraints can be modelled as max-plus system and handled by max-plus algebra which changes the original nonlinear system in the traditional sense into linear system in this framework. Min-max-plus systems are extensions of max-plus systems and nonlinear even in the max-plus algebra view. Output feedback stabilization for min–max-plus systems with min–max-plus inputs and max-plus outputs is considered in this paper. Max-plus projection representation for the closed-loop system with min–max-plus output feedback is introduced and the formula to calculate the cycle time is presented. Stabilization of reachable systems with at least one observable state and a further result for reachable and observable systems are worked out, during which max-plus output feedbacks are used to stabilize the systems. The method based on the max-plus algebra is constructive in nature.     

Fuzzy timed Petri nets — analysis and implementation

In [Z. Ding, H. Bunke, M. Schneider, A. Kandel, Fuzzy timed Petri net — definitions, properties and applications, Math. Comput. Modelling (2005) (in press)], we posed two fuzzy timed Petri Net models. Based on the mark changing rate, they can be classified either as a discrete Fuzzy Timed Petri Net model (discrete-FTPN), or as a continuous Fuzzy Timed Petri Net model (continuous-FTPN). In this paper, we present an algorithm developed to compute reachable states for discrete-FTPN models. We also present properties of the continuous-FTPN model, which are used to describe the system’s behavior. From the investigation presented in this paper, we conclude that it is easier to implement a discrete-FTPN model, but for a theoretical study the continuous-FTPN model is better.     

The General Theory of Linear Difference Equations over the Max-Plus Semi-Ring

We present the mathematical theory underlying systems of linear difference equations over the max-plus semi-ring. The result provides an analog of isomonodromy theory for ultradiscrete Painlevé equations, which are extended cellular automata, and provide evidence for their integrability. Our theory is analogous to that developed by Birkhoff and his school for linear q -difference equations, but stands independently of the latter. As an example, we derive linear problems in this algebra for ultradiscrete versions of the symmetric P_IV equation and show how it is a necessary condition for isomonodromic deformation of a linear system.     

Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra

The problem of finding one eigenvector of a given Monge matrix A in a max-plus algebra is considered. For a general matrix, the problem can be solved in O(n ³) time by computing one column of the corresponding metric matrix Δ(A _λ), where λ is the eigenvalue of A. An algorithm is presented, which computes an eigenvector of a Monge matrix in O(n ²) time.     

Analysis of stochastic min-max-plus systems: Results and conjectures

Systems in which the operations min, max and addition appear simultaneously are called min-max-plus systems. Such systems, which are extensions of timed discrete event systems (which on their turn are based on the max-plus algebra, i.e., on the operations max and addition only), have been studied for some years now [1–3]. In these references only deterministic systems were studied. In the current paper, some stochastic extensions will be considered. It will be shown that extensions of eigenvalues, Lyapunov coefficients, exist for these stochastic systems. Some conjectures will be given which are supported by characteristic examples.     

Computing an eigenvector of an inverse Monge matrix in max-plus algebra

The problem of computing an eigenvector of an inverse Monge matrix in max-plus algebra is addressed. For a general matrix, the problem can be solved in at most O(n³) time. This note presents an O(n²) algorithm for computing one max-plus algebraic eigenvector of an inverse Monge matrix . It is assumed that is irreducible.     

Max-Plus Algebra and Mathematical Fear in Dynamic Optimization

Max-plus algebra, cost measures, and mathematical fear have proved useful tools in dynamic optimization. Indeed, the first two have even become a central tool in some fields of investigation such as discrete event systems. We first recall the fundamentals of max-plus algebra with simple examples of max-plus linear models, and simple consequences of that remark. We then introduce cost measures, the natural equivalent of probability measures in the max-plus algebra, and their fundamental properties, including the definition of the mathematical fear (the equivalent of the mathematical expectation), induced measures and conditioning. Finally, we concentrate on those aspects that are put in use in dynamical optimization and state a separation theorem which was first derived using these tools.     

广义四元数的一次代数方程

本文运用广义四元数代数的矩阵表示讨论了两类广义四元数的一次代数方程的解问题，并得到了这两类代数方程有唯一解、无穷多解，无解的判别条件。     

Piecewise linear concave dynamical systems appearing in the microscopic traffic modeling

Motivated by microscopic traffic modeling, we analyze dynamical systems which have a piecewise linear concave dynamics not necessarily monotonic. We introduce a deterministic Petri net extension where edges may have negative weights. The dynamics of these Petri nets are uniquely defined and may be described by a generalized matrix with a submatrix in the standard algebra with possibly negative entries, and another submatrix in the minplus algebra. When the dynamics is additively homogeneous, a generalized additive eigenvalue is introduced, and the ergodic theory is used to define a growth rate. In the traffic example of two roads with one junction, we compute explicitly the eigenvalue and we show, by numerical simulations, that these two quantities (the additive eigenvalue and the average growth rate) are not equal, but are close to each other. With this result, we are able to extend the well-studied notion of fundamental traffic diagram (the average flow as a function of the car density on a road) to the case of roads with a junction and give a very simple analytic approximation of this diagram where four phases appear with clear traffic interpretations. Simulations show that the fundamental diagram shape obtained is also valid for systems with many junctions.     

Groups of partial differential operators and the generalized Bessel functions

Considering the generalized Bessel functions satisfying a special ordinary differential equation of mth order, we derive some addition theorems and generating functions with the help of some algebra constructed for a group of first order partial differential operators grounding on the recurrence relations for these functions.     

Solving the Inverse Generalized Problem of Vertical Seismic Profiling

The dynamic inverse seismics problem is considered in a generalized setting. We investigate whether the wave propagation problem in a vertically nonhomogeneous medium is well-posed. We show that the regular part of the solution is an L ₂ function and the inverse problem, i.e., the determination of the reflection coefficient, is thus reducible to minimizing the error functional. The gradient of the functional is obtained in explicit form from the conjugate problem, and approximate formulas for its evaluation are derived. A regularization algorithm for the solution of the inverse problem is considered; simulation results using various excitation sources are reported.     

Solution of Volterra operator-integral equations in the nonregular case by the successive approximation method

The branches of solutions of a nonlinear integral equation of Volterra type in a Banach space are constructed by the successive approximation method. We consider the case in which a solution may have an algebraic branching point. We reduce the equation to a system regular in a neighborhood of the branching point. Continuous and generalized solutions are considered. General existence theorems are used to study an initial-boundary value problem with degeneration in the leading part.     

Spectral-Parameter Dependent Yang–Baxter Operators and Yang–Baxter Systems From Algebra Structures

For any algebra, two families of colored Yang–Baxter operators are constructed, thus producing solutions to the two-parameter quantum Yang–Baxter equation. An open problem about a system of functional equations is stated. The matrix forms of these operators for two and three dimensional algebras are computed. A FRT bialgebra for one of these families is presented. Solutions for the one-parameter quantum Yang–Baxter equation are derived and a Yang–Baxter system constructed.     

Eigenvectors of interval matrices over max–plus algebra

The behaviour of a discrete-event dynamic system is often conveniently described using a matrix algebra with operations max and plus. Such a system moves forward in regular steps of length equal to the eigenvalue of the system matrix, if it is set to operate at time instants corresponding to one of its eigenvectors. However, due to imprecise measurements, it is often unappropriate to use exact matrices. One possibility to model imprecision is to use interval matrices. We show that the problem to decide whether a given vector is an eigenvector of one of the matrices in the given matrix interval is polynomial, while the complexity of the existence problem of a universal eigenvector remains open. As an aside, we propose a combinatorial method for solving two-sided systems of linear equations over the max–plus algebra.