Some decision problems on integer matrices

DOI10.1051/ita:2005007zbMath1081.20066MaRDI QIDQ4680730

Juhani Karhumäki, Christian Choffrut

Publication date: 7 June 2005

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2005__39_1_125_0

zbMATH Keywords

decision problems; integer matrices; semigroups of matrices; finitely generated semigroups; recursive decidability

Mathematics Subject Classification ID

68R15: Combinatorics on words

20M20: Semigroups of transformations, relations, partitions, etc.

20M05: Free semigroups, generators and relations, word problems

15A30: Algebraic systems of matrices

Related Items

Unnamed Item, On the Identity Problem for the Special Linear Group and the Heisenberg Group., On Affine Reachability Problems, On Reachability Problems for Low-Dimensional Matrix Semigroups, Acceptance Ambiguity for Quantum Automata, Mortality Problem for 2×2 Integer Matrices, On the membership of invertible diagonal and scalar matrices, Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\), On injectivity of quantum finite automata, On the problem of freeness of multiplicative matrix semigroups, Freeness properties of weighted and probabilistic automata over bounded languages, Some formal tools for analyzing quantum automata., On the decidability of semigroup freeness, Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$, Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$, UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS

Cites Work

• A remark on the representation of trace monoids
• The uses of 2 by 2 matrices in combinatorial group theory. A survey
• On finite semigroups of matrices
• La finitude des représentations linéaires des semi-groupes est decidable
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Unsolvability in 3 × 3 Matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item