Origin of tropical mathematics

Question

On Wikipedia, it is claimed without a source that Imre Simon founded tropical mathematics.

The first work of his I was able to find on the subject is Limited subsets of a free monoid which uses the semiring $\mathbb N \cup \{\infty\}$ (together with the operations $\min$ and $+$) in the context of automata theory and formal languages and which dates back to 1978.

My questions is: Is this the first paper in which a tropical semiring is used?

EDIT: To clarify, I am not asking for the origin of the word tropical itself. That has already been answered on this website.

I am asking for the origin of tropical mathematics: that is, the study of the tropical semiring, be it in tropical geometry, algebra or analysis, and whether it was in an applied or theoretical context.

In other words, what is the first work that studies the tropical semiring?

EDIT: I have a follow-up question on the history of the subject here

Answer 1

I asked Christian Choffrut and Dominique Perrin this question today. They essentially told me the following: certainly, the name tropical comes in honour of the Brazilian mathematician Imre Simon; and to a Frenchman, Brazil is quite tropical (this is the full depth of the naming).* As for the mathematical origins, there were many. They mentioned two.

1. The first is the following problem: let $R \subseteq A^\ast$ be a regular language. Does there exist some $n \geq 0$ such that $R^n = R^\ast$? This is an interesting problem, and tropical mathematics can be used to deal with problems of this sort. The details are unclear to me, but probably rather accessible.
2. The second comes from the Floyd-Warshall algorithm for finding minimal paths in graphs. This problem and algorithm can be interpreted in terms of min-plus automata, and this insight was part of the drive to create a larger framework of tropical mathematics.

I don't know too many of the details of these two problems, or the tropical insights that help; but I hope this was useful in answering the question somewhat! It can undoubtedly be fleshed out significantly. ${}$

${}$

*Regarding this naming, Dominique told me that M-P. Schützenberger, the PhD supervisor of both Christian and Dominique, was very fond of such plaisanteries, which probably contributed to its becoming an established term.

Answer 2

This answer is due to Benjamin Steinberg:

Simon's paper is likely the first at least to make serious use of [the tropical semiring] and it was in theoretical computer science to study star height and limitedness.

Answer 3

The paper "Limited subsets of a free monoid" was published in 1978. However, another paper

A. Mandel, I. Simon, On finite semigroups of matrices, Theoret. Comput. Sci. 5 (1977/78), no. 2, 101--111

was published sligthly earlier and also makes use of tropical semirings. In the bibliography of this paper, there is an earlier reference [9] to a report of the university of São-Paulo, with the following quote:

Finally, we mention a related problem. Let $M$ be the semiring with support $\mathbb{N} \cup \{\infty\}$, where $a \oplus b = \min\{a,b\}$ and $a \odot b = a + b$. In [9], a characterization of torsion elements of $M_n(M)$ is given (...)

[9] I. Simon, On limited events IME-USP (1974).

Thus this report is likely to be the first work on tropical semirings.

Answer 4

What is nowadays called "tropical semiring" was very explicitly defined and used by Bernard Carré in his 1971 paper An algebra for network routing problems. Its abstract:

Problems involving the determination of routes on networks arise in many different contexts. For example network flow problems in operations research, such as transportation and assignment problems, involve the determination of a succession of shortest or least-cost paths between commodity sources and sinks. Again, critical path analysis and certain scheduling problems involve the determination of longest paths on activity networks. Pathfinding problems of different kinds also arise in the design of logic networks, and in routing messages through congested communication networks. This paper presents an algebraic structure for the formulation and solution of such problems. After defining the algebraic structure and giving concrete examples applicable to different kinds of routing problems, we use it in a general analysis of a class of directed networks, in which each arc has an associated measure (representing for instance a transportation cost, an activity duration, the state (open or closed) of a switch, or the probability of a communication link being available). It is then shown that all the routing problems mentioned above can be expressed in the same algebraic form, and that they can all be solved by variants of classical methods of linear algebra, differing from these only in the significance of the additive and multiplicative operations.