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

DOI10.4230/LIPICS.MFCS.2017.19MaRDI QIDQ5111233zbMATH OpenOpenAlexFDO

Authors Laure Daviaud, Pierre Guillon, Glenn Merlet

Publication date 26 May 2020

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)

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.

Recommendations

• Max-plus automata
• On the joint spectral radius for bounded matrix languages
• Extremal matrix products and the finiteness property
• The ultimate rank of tropical matrices
• Approximate comparison of functions computed by distance automata

Cites work

• scientific article; zbMATH DE number 627763 (Why is no real title available?)
• scientific article; zbMATH DE number 1163641 (Why is no real title available?)
• scientific article; zbMATH DE number 5018129 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Approximate comparison of distance automata
• Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard
• Bounds for joint spectral radii of a set of nonnegative matrices
• Bounds for the Perron root using max eigenvalues
• Max-linear systems. Theory and algorithms.
• Modeling and analysis of timed Petri nets using heaps of pieces
• On NFAs where all states are final, initial, or both
• On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra
• On the definition of a family of automata
• Performance evaluation of (max,+) automata
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Semigroup of matrices acting on the max-plus projective space
• Series which are both max-plus and min-plus rational are unambiguous
• Size-Change Abstraction and Max-Plus Automata
• The equality problem for rational series with multiplicities in the tropical semiring is undecidable
• The ultimate rank of tropical matrices
• Universal diophantine equation
• What's decidable about weighted automata?

Cited in

(7)

• A contribution to the determinization of max-plus automata
• scientific article; zbMATH DE number 7559164 (Why is no real title available?)
• Simulations and bisimulations for max-plus automata
• Finite sequentiality of finitely ambiguous max-plus tree automata
• On the joint spectral radius for bounded matrix languages
• Max-plus automata
• Finite sequentiality of unambiguous max-plus tree 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)