Narrow Results

Obtaining exact blocking probabilities for tandem queues with finite capacities is not a trivial problem. In this paper, we propose a computational approximation method using max-plus algebra for computing blocking probability in a Poisson-driven 2-node tandem queue with finite capacities and constant service times. The blocking probability of a finite-capacity queueing system can be obtained from either the tail probability of stationary waiting time or the difference between two expected stationary waiting times at the first node of the corresponding extended 3-node tandem queue. The computational results in this study show that the proposed approach provides a good approximation of the blocking probability, and in particular, it works well under moderately to heavily loaded situations. The proposed approach is not limited to a particular blocking policy, system structure, or service time; hence, it is applicable to general queues with finite buffer capacities and various blocking policies.

Based on discrete-event dynamic system theory, train operation events in high-speed railway transportation systems are regarded as the basic elements of these dynamic systems. For non-periodic timetable railways in China, based on a max-plus algebra method, a delay propagation cellular automata model is proposed to evaluate the robustness of high-speed train operation plans. The cellular automata evolution rules that can reproduce the delay propagation state of trains mainly consider train safety headway constraints, passenger transfer constraints, and electric multiple unit (EMU) connection constraints. A simulation analysis of actual cases is performed. The simulation results show that the model can be used to evaluate the robustness of the train operation plan. The numerical results show that in the preparation of train operation plans, the proposed model can predict which trains have significant influences on delays in advance and improve the possibility of reducing the occurrence of delays to maintain high-quality service.

We consider the following matrix reachability problem: given r square matrices with entries in a semiring, is there a product of these matrices which attains a prescribed matrix? Similarly, we define the vector (resp. scalar) reachability problem, by requiring that the matrix product, acting by right multiplication on a prescribed row vector, gives another prescribed row vector (resp. when multiplied on the left and right by prescribed row and column vectors, gives a prescribed scalar). We show that over any semiring, scalar reachability reduces to vector reachability which is equivalent to matrix reachability, and that for any of these problems, the specialization to any r ≥ 2 is equivalent to the specialization to r = 2. As an application of these reductions and of a theorem of Krob, we show that when r = 2, the vector and matrix reachability problems are undecidable over the max-plus semiring (ℤ∪{-∞}, max,+). These reductions also improve known results concerning the classical zero corner problem. Finally, we show that the matrix, vector, and scalar reachability problems are decidable over semirings whose elements are "positive", like the tropical semiring (ℤ∪{+∞}, min,+).

This paper introduces the foundations of the polynomial algebra and basic structures for algebraic geometry over the extended tropical semiring. Our development, which includes the tropical version for the fundamental theorem of algebra, leads to the reduced polynomial semiring — a structure that provides a basis for developing a tropical analogue to the classical theory of commutative algebra. The use of the new notion of tropical algebraic com-sets, built upon the complements of tropical algebraic sets, eventually yields the tropical algebraic Nullstellensatz.

We study the horofunction boundary of an Artin group of dihedral type with its word metric coming from either the usual Artin generators or the dual generators. In both cases, we determine the horoboundary and say which points are Busemann points, that is, the limits of geodesic rays. In the case of the dual generators, it turns out that all boundary points are Busemann points, but this is not true for the Artin generators. We also characterize the geodesics with respect to the dual generators, which allows us to calculate the associated geodesic growth series.

In this paper we investigate algorithms based on the Fast Legendre Transform (FLT) in order to compute tabulated Equation Of State (EOS) for fluids with phase transition. The equation of state of a binary mixture is given by an energy minimization principle. According to the miscible or immiscible nature of the mixture, the energy of the system is either a convex envelope or an inf-convolution of the energies of the two phases. Because these operations are closely linked to Legendre transform, it is possible to construct fast algorithms that compute efficiently these operations. In addition, it appears that the natural mathematical tool for studying mixture thermodynamics in the Legendre space is the max-plus algebra theory.

The object of this paper is to present two algebraic results with straightforward proofs, which have interesting consequences in tropical geometry. We start with an identity for polynomials over the max-plus algebra, which shows that any polynomial divides a product of binomials. Interpreted in tropical geometry, any tropical variety W can be completed to a union of tropical primitives, i.e. single-face polyhedral complexes. In certain situations, a tropical variety W has a "reversal" variety, which together with W already yields the union of primitives; this phenomenon is explained in terms of a map defined on the algebraic structure, and yields a duality on tropical hypersurfaces.

This paper proposes the matrix representation of formal polynomials over max-plus algebra and obtains the maximum and minimum canonical forms of a polynomial function by standardizing this representation into a canonical form. A necessary and sufficient condition for two formal polynomials corresponding to the same polynomial function is derived. Such a matrix method is constructive and intuitive, and leads to a polynomial algorithm for factorization of polynomial functions. Some illustrative examples are presented to demonstrate the results.

The synchronization of legs in many-legged robots is a combinatorial problem that can be very critical for successful climbing or locomotion in very rough terrain. This paper addresses developing gait generation controllers with desirable synchronization properties by introducing a number of abstractions in the traditional modeling approaches. It describes how to use the max-plus algebra as a modeling tool for discrete-event systems and how it can be applied to legged locomotion.