In this paper, we are interested in the general problem of estimating a linear function of the states for a given Max-Plus linear dynamical system. More precisely, using only the current and past ...inputs/outputs of the system, we want to construct a sequence that converges in a finite number of steps to the value given by a linear function of the states, for all initial conditions of the system. We provide necessary and sufficient conditions to solve this general problem. We also define and study a Max-Plus version of the well-known Luenberger observer, which is a subclass of the general problem that we are interested in, and we also provide necessary and sufficient conditions to solve this particular problem of observer synthesis. Finally, we show that there are important connections between results in the Max-Plus domain and associated results in the standard linear systems theory.
In this paper we investigate the number partitioning problem, using the tropical semiring (max-plus algebra). We show that the problem is reduced to deciding whether one of integers is a solution of ...a tropical analogue of algebraic equations with coefficients composed of other integers. For n up to 6 we derive concretely and explicitly the equation and its solution set. The derivation requires only routine algebraic computations, so can be applied for n larger than 6. Our approach based on max-plus algebra reveals the mathematical structure of the problem and provides a new view point for the P versus NP problem, since the problem is well-known to be NP-complete.
The purpose of this article is to provide a viewpoint of the development of the field of Discrete Event Systems (DES). Necessarily incomplete, because of the breath of topics and richness of research ...results, this paper is mainly presented from a System Theory-Automatic Control (AC) perspective. Written with a certain emphasis at the dawn of the discipline, the following five articles of this special section of the journal provide essential complements on its evolution along the four last decades. Starting with the identification of three basic threads along which many developments took place, the multidisciplinary and dynamic character of DES and the diversity of formalisms and techniques that are used are stressed.
Cryptography has a role to secure an important information. Until now, many varieties of cryptographic algorithms are available in the literature. In this paper, we propose a cryptographic algorithm ...based on Type IVa max-plus wavelet transforms (MP-Wavelets). Encryption and decryption algorithms are constructed based on the analysis and synthesis process of Type IVa MP-Wavelets, respectively. The encryption key contains the number of channels in all levels. The encryption key is chosen such that multiplication of the number of channels in all levels is greater than or equal to the number of characters in the Plaintext. The decryption key consists of the encryption key and a sequence generated by the binary encoding of detail components. This guarantees that the decryption key is very difficult to obtain using the brute-force method. The cryptographic process involves only maximization and addition operations as main operations. The experiments and analysis show that the algorithm is a good cryptographic algorithm based on the correlation between Plaintext and Ciphertext, encryption quality, the decryption key space, cryptanalysis (Ciphertext-only attack) and security analysis (entropy analysis, key sensitivity, Plaintext sensitivity). This algorithm is also efficient in the running time, because the complexity is linear w.r.t.the number of characters in the Plaintext.
In this paper we present new theory and algorithms for 2-norm regression over the max-plus semiring. As an application we also show how max-plus 2-norm regression can be used in system identification ...of max-plus linear dynamical systems with Gaussian noise. We also introduce and provide methods for solving a max-plus linear inverse problem with regularization, which can be used when the original problem is not well posed.
A max-plus matrix A (operations max and plus are denoted by ⊕ and ⊗, respectively) is called X–robust if the orbit x,A⊗x,A2⊗x,… of any initial vector x belonging to the interval X={x:x̲≤x≤x¯} ends up ...with a max-plus algebraic eigenvector of A. The X–robustness of a max-plus matrix is extended to interval vectors X using forall–exists quantification of their interval entries (so-called XAE–robustness and XEA–robustness). A complete characterization of XAE–robustness and XEA–robustness of matrices and possible (universal) XAE (XEA)–robustness of interval circulant matrices is presented.
Boolean matrices are of prime importance in the study of discrete event systems (DES), which allow us to model systems across a variety of applications. The index of convergence (i.e. the number of ...distinct powers of a Boolean matrix) is a crucial characteristic in that it assesses the transient behaviour of the system until reaching a periodic course. In this paper, adopting a graph-theoretic approach, we present bounds for the index of convergence of Boolean matrices for a diverse class of systems, with a certain decomposition. The presented bounds are an extension of the bound on irreducible Boolean matrices, and we provide non-trivial bounds that were unknown for classes of systems. Furthermore, the proposed method is able to determine the bounds in polynomial time. Lastly, we illustrate how the new bounds compare with the previously known bounds and we show their effectiveness in cases such as the benchmark IEEE 5-bus power system.
A closed form of the L-localized solution set of an interval linear system with max-plus algebra is a finite union of interval vectors. This paper analyzes and proves some properties to reduce number ...of the union sets to be a smaller number of the union of interval vectors that are not subsets of each other. This result helps simplify the feasible set of an optimization problem with max-plus linear equation constraints.
In this paper we consider applications of max-plus algebra to flow shop scheduling problems. Our aim is to show that max-plus algebra is useful for flow shop scheduling. We present two new solvable ...conditions in m-machine permutation flow shops using max-plus algebra. One of the conditions is found by considering a max-plus algebraic analogue of a proposition in linear algebra. The other is derived using a new framework, which associates a machine with a matrix and is the dual of the max-plus approach associating a job with a matrix by Bouquard, Lenté, and Billaut (2006). The framework is the first one which can deal with non-permutation flow shop problems based on max-plus algebra. Moreover, using the framework, we provide new simple proofs of some known results.
A walk on max-plus algebra Watanabe, Sennosuke; Fukuda, Akiko; Segawa, Etsuo ...
Linear algebra and its applications,
08/2020, Letnik:
598
Journal Article
Recenzirano
Max-plus algebra is a kind of idempotent semiring over Rmax:=R∪{−∞} with two operations ⊕:=max and ⊗:=+. In this paper, we introduce a new model of a walk on one dimensional lattice on Z, as an ...analogue of the quantum walk, over the max-plus algebra and we call it max-plus walk. In the conventional quantum walk, the summation of the ℓ2-norm of the states over all the positions is a conserved quantity. In contrast, the summation of eigenvalues of state decision matrices is a conserved quantity in the max-plus walk. Moreover, spectral analysis on the total time evolution operator is also given.
PDF
