2026-07-22T11:37:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8105 2024-03-06T10:40:51Z ddc:004 open_access

Comparison of Max-Plus Automata and Joint Spectral Radius of Tropical Matrices Daviaud, Laure Guillon, Pierre Merlet, Glenn max-plus automata max-plus matrices weighted automata tropical semiring joint spectral radius ultimate rank Weighted automata over the tropical semiring Zmax are closely related to finitely generated semigroups of matrices over Zmax. In this paper, we use results in automata theory to study two quantities associated with sets of matrices: the joint spectral radius and the ultimate rank. We prove that these two quantities are not computable over the tropical semiring, i.e. there is no algorithm that takes as input a finite set of matrices S and provides as output the joint spectral radius (resp. the ultimate rank) of S. On the other hand, we prove that the joint spectral radius is nevertheless approximable and we exhibit restricted cases in which the joint spectral radius and the ultimate rank are computable. To reach this aim, we study the problem of comparing functions computed by weighted automata over the tropical semiring. This problem is known to be undecidable, and we prove that it remains undecidable in some specific subclasses of automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laure Daviaud and Pierre Guillon and Glenn Merlet 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.19 urn:nbn:de:0030-drops-81052 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode