REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS

DOI10.1142/S021819670600313XzbMATH Open1108.20057arXivmath/0310028OpenAlexW1999099378MaRDI QIDQ5483458FDOQ5483458

Authors: Stéphane Gaubert, Ricardo D. Katz 

Publication date: 14 August 2006

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Abstract: We consider the following matrix reachability problem: given $r$ square matrices with entries in a semiring, is there a product of these matrices which attains a prescribed matrix? We define similarly the vector (resp. scalar) reachability problem, by requiring that the matrix product, acting by right multiplication on a prescribed row vector, gives another prescribed row vector (resp. when multiplied at left and right by prescribed row and column vectors, gives a prescribed scalar). We show that over any semiring, scalar reachability reduces to vector reachability which is equivalent to matrix reachability, and that for any of these problems, the specialization to any $rgeq2$ is equivalent to the specialization to $r=2$. As an application of this result and of a theorem of Krob, we show that when $r=2$, the vector and matrix reachability problems are undecidable over the max-plus semiring $(Zcup-infty,max,+)$. We also show that the matrix, vector, and scalar reachability problems are decidable over semirings whose elements are ``positive, like the tropical semiring $(Ncup+infty,min,+)$.

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

Recommendations

• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• scientific article; zbMATH DE number 1163636
• On undecidability bounds for matrix decision problems
• On the computational complexity of matrix semigroup problems
• Lowering Undecidability Bounds for Decision Questions in Matrices

zbMATH Keywords

mortalitysemigroupsmatrix semigroupsdecision problemsorbit problemmembership problemalgorithmic decidabilitytropical semiringsscalar reachability problemvector reachability problemmatrix reachability problem

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Combinatorics on words (68R15) Attainable sets, reachability (93B03) Semirings (16Y60) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Enumerative combinatorics. Volume 2.
• Title not available (Why is that?)
• On semigroups of matrices over the tropical semiring
• Modeling and analysis of timed Petri nets using heaps of pieces
• When is a pair of matrices mortal?
• Unsolvability in 3 × 3 Matrices
• Limitedness theorem on finite automata with distance functions
• Title not available (Why is that?)
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• A survey of computational complexity results in systems and control
• Polynomial-time algorithm for the orbit problem
• Performance evaluation of (max,+) automata
• The mortality problem for matrices of low dimensions
• The free partially commutative Lie algebra: Bases and ranks
• On the Burnside problem for semigroups of matrices in the \((\max,+)\) algebra
• Improved limitedness theorems on finite automata with distance functions
• Examples of undecidable problems for 2-generator matrix semigroups
• Minimizing subsequential transducers: a survey.
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• Mortality in Matrix Semigroups
• The Complexity of theA B CProblem
• Some consequences of a Fatou property of the tropical semiring

Cited In (18)

• Comparison of max-plus automata and joint spectral radius of tropical matrices
• Vector reachability problem in \(\operatorname{SL}(2,\mathbb{Z})\)
• Weighted automata on infinite words in the context of attacker-defender games
• On undecidability bounds for matrix decision problems
• Semigroup identities of tropical matrix semigroups of maximal rank
• Reachability problems in quaternion matrix and rotation semigroups
• On the topological structure of a finitely generated semigroup of matrices
• Semigroup identities in the monoid of two-by-two tropical matrices.
• Reachability Problems in Quaternion Matrix and Rotation Semigroups
• Computational techniques for reachability analysis of Max-Plus-Linear systems
• Multiplicative structure of \(2\times 2\) tropical matrices
• Improved matrix pair undecidability results
• Undecidability bounds for integer matrices using Claus instances
• Mathematical Foundations of Computer Science 2004
• Rational semimodules over the max-plus semiring and geometric approach to discrete event systems.
• Developments in Language Theory
• Semigroup identities in the monoid of triangular tropical matrices.
• Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings

This page was built for publication: REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS

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