Comparison of max-plus automata and joint spectral radius of tropical matrices

Daviaud, Laure, Guillon, Pierre and Merlet, Glenn (2017) Comparison of max-plus automata and joint spectral radius of tropical matrices. In: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017. Leibniz International Proceedings in Informatics, LIPIcs . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, DNK. ISBN 9783959770460

Full text not available from this repository.

Abstract

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.

Item Type:	Book Section
Additional Information:	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.
Uncontrolled Keywords:	joint spectral radius,max-plus automata,max-plus matrices,tropical semiring,ultimate rank,weighted automata,software ,/dk/atira/pure/subjectarea/asjc/1700/1712
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	08 Jun 2023 14:30
Last Modified:	08 Jun 2023 14:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92344
DOI:	10.4230/LIPIcs.MFCS.2017.19

Actions (login required)

View Item