Some consequences of a Fatou property of the tropical semiring (Q1326758): Difference between revisions

The tropical semiring \(\mathcal M\) is the semiring \(\mathbb{N} \cup \{+ \infty\}\) with sum \(\min(a,b)\) and product \(a + b\). It is shown that \(\mathbb{Z}_{\min} = \mathbb{Z} \cup \{+ \infty\}\) (with the same operations) is a Fatou extension of \(\mathcal M\); that is, each noncommutative rational series over \(\mathbb{Z}_{\min}\), which has coefficients in \(\mathcal M\), is rational over \(\mathcal M\). The equality problem for rational series over \(\mathcal M\) or \(\mathbb{Z}_{\min}\) is undecidable. However, it is decidable for a series which is both \(\mathbb{Z}_{\min}\)- and \(\mathbb{Z}_{\max}\)-rational. An application to the limitedness problem is also given.