Given a finite set of matrices with integer entries, consider the question of determining whether the semigroup they generated 1) is free; 2) contains the identity matrix; 3) contains the null matrix or 4) is a group. Even for matrices of dimension
@article{ITA_2005__39_1_125_0, author = {Choffrut, Christian and Karhum\"aki, Juhani}, title = {Some decision problems on integer matrices}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {125--131}, publisher = {EDP-Sciences}, volume = {39}, number = {1}, year = {2005}, doi = {10.1051/ita:2005007}, mrnumber = {2132582}, zbl = {1081.20066}, language = {en}, url = {https://www.numdam.org/articles/10.1051/ita:2005007/} }
TY - JOUR AU - Choffrut, Christian AU - Karhumäki, Juhani TI - Some decision problems on integer matrices JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 125 EP - 131 VL - 39 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ita:2005007/ DO - 10.1051/ita:2005007 LA - en ID - ITA_2005__39_1_125_0 ER -
%0 Journal Article %A Choffrut, Christian %A Karhumäki, Juhani %T Some decision problems on integer matrices %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 125-131 %V 39 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ita:2005007/ %R 10.1051/ita:2005007 %G en %F ITA_2005__39_1_125_0
Choffrut, Christian; Karhumäki, Juhani. Some decision problems on integer matrices. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 125-131. doi : 10.1051/ita:2005007. https://www.numdam.org/articles/10.1051/ita:2005007/
[1] Transductions and context-free languages. B.G. Teubner (1979). | MR | Zbl
,[2] On the undecidability of freeness of matrix semigroups. Internat. J. Algebra Comput. 9 (1999) 295-305. | Zbl
, and ,[3] A remark on the representation of trace monoids. Semigroup Forum 40 (1990) 143-152. | Zbl
,[4] Unique decipherability for partially commutative alphabets. Fund. Inform. X (1987) 323-336. | Zbl
and ,[5] Automata, Languages and Machines, Vol. A. Academic Press (1974). | MR | Zbl
,[6] Decision questions on integer matrices. Lect. Notes Comp. Sci. 2295 (2002) 57-68. | Zbl
,[7] Morphisms, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa. Springer-Verlag 1 (1997) 439-510. | Zbl
and ,[8] La finitude des représentations linéaires de semigroupes est décidable. J. Algebra 52 (1978) 437-459. | Zbl
,[9] Some opem problems in combinatorics of words and related areas, in Proc. of RIMS Symposium on Algebraic Systems, Formal Languages and Computation. RIMS Institute 1166 (2000) 118-130. | Zbl
,[10] On the undecidability of the freeness of integer matrix semigroups monoids. Internat. J. Algebra Comput. 1 (1991) 223-226. | Zbl
, and ,[11] Combinatorial Group Theory, of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag 89 (1977). | MR | Zbl
and ,[12] The use of 2 by 2 matrices in combinatorial group theory. Resultate der Mathematik 4 (1981) 171-192. | Zbl
,[13] On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1978) 101-112. | Zbl
and ,[14] On certain insoluble problems concerning matrices (russian). Doklady Akad. Nauk SSSR (N.S.) 57 (1947) 539-542. | Zbl
,[15] Open problems in group theory: http://zebra.sci.ccny.edu/cgi-bin/LINK.CGI?/www/web/problems/oproblems.html
[16] Unsolvability in
[17] An introduction to the Theory of Groups. Ally and Bacon Inc. (1965). | MR | Zbl
,- The membership problem for subsemigroups of GL2(Z) is NP-complete, Information and Computation, Volume 296 (2024), p. 105132 | DOI:10.1016/j.ic.2023.105132
- , Proceedings of the 56th Annual ACM Symposium on Theory of Computing (2024), p. 884 | DOI:10.1145/3618260.3649609
- Semigroup Intersection Problems in the Heisenberg Groups, SIAM Journal on Discrete Mathematics, Volume 38 (2024) no. 4, p. 3176 | DOI:10.1137/23m1581467
- Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings, Theoretical Computer Science, Volume 1002 (2024), p. 114599 | DOI:10.1016/j.tcs.2024.114599
- Membership Problems in Infinite Groups, Twenty Years of Theoretical and Practical Synergies, Volume 14773 (2024), p. 44 | DOI:10.1007/978-3-031-64309-5_5
- , 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2023), p. 1 | DOI:10.1109/lics56636.2023.10175768
- Recent Advances in Algorithmic Problems for Semigroups, ACM SIGLOG News, Volume 10 (2023) no. 4, p. 3 | DOI:10.1145/3636362.3636365
- On the Identity and Group Problems for Complex Heisenberg Matrices, Reachability Problems, Volume 14235 (2023), p. 42 | DOI:10.1007/978-3-031-45286-4_4
- On injectivity of quantum finite automata, Journal of Computer and System Sciences, Volume 122 (2021), p. 19 | DOI:10.1016/j.jcss.2021.05.002
- Freeness properties of weighted and probabilistic automata over bounded languages, Information and Computation, Volume 269 (2019), p. 104440 | DOI:10.1016/j.ic.2019.104440
- Vector and scalar reachability problems in SL(2,Z), Journal of Computer and System Sciences, Volume 100 (2019), p. 30 | DOI:10.1016/j.jcss.2018.09.003
- On the Decidability of Membership in Matrix-exponential Semigroups, Journal of the ACM, Volume 66 (2019) no. 3, p. 1 | DOI:10.1145/3286487
- Matrix Semigroup Freeness Problems in SL
, SOFSEM 2017: Theory and Practice of Computer Science, Volume 10139 (2017), p. 268 | DOI:10.1007/978-3-319-51963-0_21 - Vector Ambiguity and Freeness Problems in SL
, Theory and Applications of Models of Computation, Volume 10185 (2017), p. 373 | DOI:10.1007/978-3-319-55911-7_27 - Mortality for 2 ×2 Matrices Is NP-Hard, Mathematical Foundations of Computer Science 2012, Volume 7464 (2012), p. 148 | DOI:10.1007/978-3-642-32589-2_16
- On the decidability of semigroup freeness, RAIRO - Theoretical Informatics and Applications, Volume 46 (2012) no. 3, p. 355 | DOI:10.1051/ita/2012010
- ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, International Journal of Foundations of Computer Science, Volume 21 (2010) no. 06, p. 963 | DOI:10.1142/s0129054110007660
- On the problem of freeness of multiplicative matrix semigroups, Theoretical Computer Science, Volume 411 (2010) no. 7-9, p. 1115 | DOI:10.1016/j.tcs.2009.12.005
- The Identity Correspondence Problem and Its Applications, Algorithms and Computation, Volume 5878 (2009), p. 657 | DOI:10.1007/978-3-642-10631-6_67
- UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, International Journal of Foundations of Computer Science, Volume 18 (2007) no. 05, p. 931 | DOI:10.1142/s0129054107005066
- On the membership of invertible diagonal and scalar matrices, Theoretical Computer Science, Volume 372 (2007) no. 1, p. 37 | DOI:10.1016/j.tcs.2006.11.011
- Some formal tools for analyzing quantum automata, Theoretical Computer Science, Volume 356 (2006) no. 1-2, p. 14 | DOI:10.1016/j.tcs.2006.01.042
Cité par 22 documents. Sources : Crossref