On semigroups of matrices over the tropical semiring. (English) Zbl 0888.68086

Summary: The tropical semiring \(\mathcal M\) consists of the set of natural numbers extended with infinity, equipped with the operations of taking minimums (as semiring addition) and addition (as semiring multiplication). We use factorization forests to prove finiteness results related to semigroups of matrices over \(\mathcal M\). Our method is used to recover results of Hashiguchi, Leung and the author in a unified combinatorial framework.


68Q45 Formal languages and automata
68R05 Combinatorics in computer science
Full Text: DOI EuDML


[1] 1. S. EILENBERG, Automata, Languages, and Machines, Volume A, Academic Press, New York, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[2] 2. K. HASHIGUCHI, Limitedness theorem on finite automata with distance functions, J. Comput. Syst. Sci., 1982, 24, pp. 233-244. Zbl0513.68051 MR661652 · Zbl 0513.68051
[3] 3. K. HASHIGUCHI, Improved limitedness theorems on finite automata with distance functions, Theoretical Comput. Sci., 1990, 72. Zbl0693.68031 MR1065598 · Zbl 0693.68031
[4] 4. H. LEUNG, An Algebraic Method for Solving Decision Problems in Finite Automata Theory, PhD thesis, Department of Computer Science, The Pennsylvania State University, 1987.
[5] 5. H. LEUNG, On the topological structure of a finitely generated semigroup of matrices, Semigroup Forum, 1988, 37, pp. 273-287. Zbl0646.20056 MR944662 · Zbl 0646.20056
[6] 6. I. SIMON, Limited subsets of a free monoid, In Proc. 19th Annual Symposium on Foundations of Computer Science, Piscataway, N. J., 1978, Institute of Electrical and Electronics Engineers, pp. 143-150. MR539835
[7] 7. I. SIMON, Recognizable sets with multiplicities in the tropical semiring. In M. P. Chytil, L. Janiga, and V. Koubek, Eds., Mathematical Foundations of Computer Science, Berlin, 1988. Springer-Verlag, Lectures Notes in Computer Science, 324, pp. 107-120. Zbl0656.68086 MR1023416 · Zbl 0656.68086
[8] 8. I. SIMON, Factorization forests of finite height, Theoretical Comput. Sci., 1990, 72, pp. 65-94. Zbl0693.68044 MR1065601 · Zbl 0693.68044
[9] 9. I. SIMON, The nondeterministic complexity of a finite automaton, In M. Lothaire, Ed, Mots - mélanges offerts à M. P. Schützenberger, Hermès, Paris, 1990, pp. 384-400. MR1252678
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.