REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS

DOI10.1142/S021819670600313XMaRDI QIDQ5483458zbMATH OpenOpenAlexFDO

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)

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

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)

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,+)$.

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

Cites work

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

Cited in

(18)

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

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)