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].

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