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

algorithmic decidabilitydecision problemsmatrix reachability problemmatrix semigroupsmembership problemmortalityorbit problemscalar reachability problemsemigroupstropical semiringsvector reachability problem

Mathematics Subject Classification ID

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

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

• A survey of computational complexity results in systems and control
• Enumerative combinatorics. Volume 2.
• Examples of undecidable problems for 2-generator matrix semigroups
• 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?)
• 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 Complexity of theA B CProblem
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• 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

(19)

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

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)