# zbMATH — the first resource for mathematics

Tropical semirings. (English) Zbl 0909.16028
Gunawardena, Jeremy (ed.), Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994, Cambridge: Cambridge University Press. 50-69 (1998).
The paper is a brief self-contained introduction in some decidability problems for sets of matrices over semirings $$(k,+,\cdot)$$ as well as in such problems for rational languages. The connection between both types of problems comes from the matrix representation of $$k$$-automata which serve as recognizers for the languages. Here a semiring is always an additively commutative one with absorbing zero and identity. Moreover, in most results which are cited, $$(k,+,\cdot)$$ is a tropical semiring, i.e., $$k=\mathbb{N}\cup\{\infty\}$$ or $$k=\mathbb{Z}\cup\{\infty\}$$ or $$k=\mathbb{R}\cup\{\infty\}$$ or similar, and $$a+b=\min(a,b)$$ and $$a\cdot b=a+b$$, the latter in the usual meaning on the particular set $$k$$. The problems under consideration are: Burnside problem, finiteness problem, finite section problem, finite power property problem, polynomial closure problem.
For the entire collection see [Zbl 0882.00035].

##### MSC:
 16Y60 Semirings 68Q45 Formal languages and automata 68Q70 Algebraic theory of languages and automata 20M35 Semigroups in automata theory, linguistics, etc.