Some decision problems on integer matrices

DOI10.1051/ita:2005007zbMath1081.20066OpenAlexW1989605444MaRDI 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 problemsinteger matricessemigroups of matricesfinitely generated semigroupsrecursive decidability

Mathematics Subject Classification ID

Combinatorics on words (68R15) Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Algebraic systems of matrices (15A30)

Related Items

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

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