REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS

DOI10.1142/S021819670600313XzbMath1108.20057arXivmath/0310028OpenAlexW1999099378MaRDI QIDQ5483458

Ricardo D. Katz, Stéphane Gaubert

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

semigroupsdecision problemsmortalitymembership problemmatrix semigroupsorbit problemalgorithmic decidabilitytropical semiringsscalar reachability problemvector reachability problemmatrix reachability problem

Mathematics Subject Classification ID

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

Related Items (11)

Semigroup identities of tropical matrix semigroups of maximal rank ⋮ Improved matrix pair undecidability results ⋮ 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 ⋮ Semigroup identities in the monoid of two-by-two tropical matrices. ⋮ Multiplicative structure of \(2\times 2\) tropical matrices ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES ⋮ Unnamed Item ⋮ Comparison of max-plus automata and joint spectral radius of tropical matrices

Cites Work

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

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