TY - GEN
T1 - Comparison of max-plus automata and joint spectral radius of tropical matrices
AU - Daviaud, Laure
AU - Guillon, Pierre
AU - Merlet, Glenn
N1 - Funding Information:
∗ The first author was partly supported by ANR Project ELICA ANR-14-CE25-0005, by ANR Project RECRE ANR-11-BS02-0010 and by project LIPA that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 683080).
Publisher Copyright:
© Laure Daviaud, Pierre Guillon, and Glenn Merlet; licensed under Creative Commons License CC-BY.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - Weighted automata over the tropical semiring Zmax = (Z[{-∞}, max, +) 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 ω and provides as output the joint spectral radius (resp. the ultimate rank) of ω. 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.
AB - Weighted automata over the tropical semiring Zmax = (Z[{-∞}, max, +) 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 ω and provides as output the joint spectral radius (resp. the ultimate rank) of ω. 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.
KW - Joint spectral radius
KW - Max-plus automata
KW - Max-plus matrices
KW - Tropical semiring
KW - Ultimate rank
KW - Weighted automata
UR - http://www.scopus.com/inward/record.url?scp=85038432994&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2017.19
DO - 10.4230/LIPIcs.MFCS.2017.19
M3 - Conference contribution
AN - SCOPUS:85038432994
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
A2 - Larsen, Kim G.
A2 - Raskin, Jean-Francois
A2 - Bodlaender, Hans L.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Y2 - 21 August 2017 through 25 August 2017
ER -