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

DOI10.4230/LIPICS.MFCS.2017.19zbMATH Open1441.68119arXiv1612.02647OpenAlexW2963247938MaRDI QIDQ5111233FDOQ5111233

Laure Daviaud, Pierre Guillon, Glenn Merlet

Publication date: 26 May 2020

Abstract: Weighted automata over the max-plus semiring S are closely related to finitely generated semigroups of matrices over S. 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 M and provides as output the joint spectral radius (resp. the ultimate rank) of M. 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.

Full work available at URL: https://arxiv.org/abs/1612.02647

zbMATH Keywords

tropical semiringweighted automatajoint spectral radiusmax-plus automatamax-plus matricesultimate rank

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Max-plus and related algebras (15A80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Max-linear Systems: Theory and Algorithms
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• On the definition of a family of automata
• Modeling and analysis of timed Petri nets using heaps of pieces
• The ultimate rank of tropical matrices
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• Semigroup of matrices acting on the max-plus projective space
• Performance evaluation of (max,+) automata
• On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra
• Bounds for the Perron root using max eigenvalues
• Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard
• What’s Decidable about Weighted Automata?
• Universal diophantine equation
• On NFAs where all states are final, initial, or both
• The equality problem for rational series with multiplicities in the tropical semiring is undecidable
• Size-Change Abstraction and Max-Plus Automata
• Series which are both max-plus and min-plus rational are unambiguous
• Bounds for joint spectral radii of a set of nonnegative matrices

Cited In (5)

• Title not available (Why is that?)
• Simulations and bisimulations for max-plus automata
• Finite sequentiality of finitely ambiguous max-plus tree automata
• Finite sequentiality of unambiguous max-plus tree automata
• A contribution to the determinization of max-plus automata

This page was built for publication: Comparison of max-plus automata and joint spectral radius of tropical matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111233)