On the decidability of semigroup freeness
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 355-399.

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability of the freeness problem over three-by-three integer matrices. Both results led to the publication of many subsequent papers. The aim of the present paper is (i) to present general results about freeness problems, (ii) to study the decidability of freeness problems over various particular semigroups (special attention is devoted to multiplicative matrix semigroups), and (iii) to propose precise, challenging open questions in order to promote the study of the topic.

DOI : https://doi.org/10.1051/ita/2012010
Classification : 20M05,  03B25,  15A30
Mots clés : decidability, semigroup freeness, matrix semigroups, post correspondence problem
@article{ITA_2012__46_3_355_0,
     author = {Cassaigne, Julien and Nicolas, Francois},
     title = {On the decidability of semigroup freeness},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {355--399},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {3},
     year = {2012},
     doi = {10.1051/ita/2012010},
     zbl = {1252.20050},
     mrnumber = {2981675},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2012010/}
}
TY  - JOUR
AU  - Cassaigne, Julien
AU  - Nicolas, Francois
TI  - On the decidability of semigroup freeness
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
DA  - 2012///
SP  - 355
EP  - 399
VL  - 46
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2012010/
UR  - https://zbmath.org/?q=an%3A1252.20050
UR  - https://www.ams.org/mathscinet-getitem?mr=2981675
UR  - https://doi.org/10.1051/ita/2012010
DO  - 10.1051/ita/2012010
LA  - en
ID  - ITA_2012__46_3_355_0
ER  - 
Cassaigne, Julien; Nicolas, Francois. On the decidability of semigroup freeness. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 355-399. doi : 10.1051/ita/2012010. http://www.numdam.org/articles/10.1051/ita/2012010/

[1] A.F. Beardon, Pell's equation and two generator free Möbius groups. Bull. London Math. Soc. 25 (1993) 527-532. | MR 1245077 | Zbl 0792.30031

[2] P. Bell and I. Potapov, Reachability problems in quaternion matrix and rotation semigroups. Inform. Comput. 206 (2008) 1353-1361. | MR 2457658 | Zbl 1151.03021

[3] M. Benois, Parties rationnelles du groupe libre. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, Série A 269 (1969) 1188-1190. | MR 265496 | Zbl 0214.03903

[4] J. Berstel, D. Perrin and C. Reutenauer, Codes and Automata, in Encycl. Math. Appl. 129 (2009). | MR 2567477 | Zbl 1187.94001

[5] V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst. 36 (2003) 231-245. | MR 1962327 | Zbl 1039.68061

[6] V.D. Blondel and J.N. Tsitsiklis, When is a pair of matrices mortal? Inf. Proc. Lett. 63 (1997) 283-286. | MR 1475343

[7] V.D. Blondel and J.N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable. Syst. Control Lett. 41 (2000) 135-140. | MR 1831027 | Zbl 0985.93042

[8] V.D. Blondel, J. Cassaigne and J. Karhumäki, Freeness of multiplicative matrix semigroups, in Unsolved problems in mathematical systems and control theory, edited by V.D. Blondel and A. Megretski. Princeton University Press (2004) 309-314. | MR 2083242

[9] O. Bournez and M. Branicky, The mortality problem for matrices of low dimensions. Theor. Comput. Syst. 35 (2002) 433-448. | MR 1909045 | Zbl 1016.68038

[10] J.L. Brenner and A. Charnow, Free semigroups of 2 × 2 matrices. Pacific J. Math. 77 (1978) 57-69. | MR 507620 | Zbl 0382.20044

[11] J. Cassaigne, T. Harju and J. Karhumäki, On the undecidability of freeness of matrix semigroups. Int. J. Algebra Comput. 9 (1999) 295-305. | MR 1723469 | Zbl 1029.20027

[12] C. Choffrut and J. Karhumäki, Some decision problems on integer matrices. RAIRO - Theor. Inf. Appl. 39 (2005) 125-131. | Numdam | MR 2132582 | Zbl 1081.20066

[13] V. Claus, Some remarks on PCP(k) and related problems. Bull. Eur. Assoc. Theoret. Comput. Sci. 12 (1980) 54-61.

[14] A. Ehrenfeucht, J. Karhumäki and G. Rozenberg, The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982) 119-144. | MR 677104 | Zbl 0493.68076

[15] P. Gawrychowski, M. Gutan and A. Kisielewic, On the problem of freeness of multiplicative matrix semigroups. Theoret. Comput. Sci. 411 (2010) 1115-1120. | MR 2606048 | Zbl 1193.15014

[16] R.H. Gilman, Computations with rational subsets of confluent groups, in Proc. of the 3rd International Symposium on Symbolic and Algebraic Computation (EUROSAM 84), edited by J. Fitch. Lect. Notes Comput. Sci. 174 (1984) 207-212. | MR 779127 | Zbl 0549.68025

[17] Z. Grunschlag, Algorithms in Geometric Group Theory. Ph.D. thesis, Graduate division of the University of California at Berkeley (1999). | MR 2699134

[18] A. Grytczuk and M. Wójtowicz, Beardon's diophantine equations and non-free Möbius groups. Bull. Lond. Math. Soc. 32 (2000) 305-310. | Zbl 1024.11016

[19] L. Guyot, Private Communication (2008).

[20] V. Halava and T. Harju, Mortality in matrix semigroups. Am. Math. Mon. 108 (2001) 649-653. | MR 1862104 | Zbl 0992.03052

[21] V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post correspondence problem. Theoret. Comput. Sci. 276 (2002) 183-204. | MR 1896352 | Zbl 1023.03038

[22] V. Halava, T. Harju and M. Hirvensalo, Undecidability bounds for integer matrices using Claus instances. Int. J. Found. Comput. Sci. 18 (2007) 931-948. | MR 2363737 | Zbl 1202.03052

[23] T. Harju and J. Karhumäki, Morphisms, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa 1 (1997) 439-510. | MR 1469999 | Zbl 0866.68057

[24] J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation, 2nd edition. Addison-Wesley (2001). | MR 645539 | Zbl 0980.68066

[25] R.A. Horn and C.R. Johnson, Matrix analysis. Corrected reprint of the 1985 original. Cambridge University Press (1990). | MR 1084815 | Zbl 0704.15002

[26] G. Jacob, Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoret. Comput. Sci. 5 (1977) 183-204. | MR 473075 | Zbl 0388.15001

[27] G.J. Janusz, Algebraic number fields, in Pure Appl. Math. 55 (1973). | MR 366864 | Zbl 0307.12001

[28] M. Kambites, P.V. Silva and B. Steinberg, On the rational subset problem for groups. J. Algebra 309 (2007) 622-639. | MR 2303197 | Zbl 1123.20047

[29] R. Kannan and R.J. Lipton, Polynomial-time algorithm for the orbit problem. J. Assoc. Comput. Mach. 33 (1986) 808-821. | MR 860527

[30] D.A. Klarner, J.-C. Birget and W. Satterfield, On the undecidability of the freeness of integer matrix semigroups. Int. J. Algebra Comput. 1 (1991) 223-226. | MR 1128014 | Zbl 0724.20036

[31] M. Krom and M. Krom, More on mortality. Am. Math. Mon. 97 (1990) 37-38. | Zbl 0702.15017

[32] M. Lothaire, Combinatorics on words, 2nd edition. Cambridge Mathematical Library, Cambridge University Press (1997). | MR 1475463 | Zbl 0874.20040

[33] M. Lothaire, Algebraic combinatorics on words, in Encycl. Math. Appl. 90 (2002). | MR 1905123 | Zbl 1001.68093

[34] R.C. Lyndon and P.E. Schupp, Combinatorial group theory, in Ergebnisse der Mathematik und ihrer Grenzgebiete 89 (1977). | MR 577064 | Zbl 0368.20023

[35] A. Mandel and I. Simon, On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1977) 101-111. | MR 473070 | Zbl 0368.20049

[36] Yu. Matiyasevich and G. Sénizergues, Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci. 330 (2005) 145-169. | MR 2112772 | Zbl 1078.03033

[37] F. Mazoit, Autour de quelques problèmes de décidabilité sur des semigroupes de matrices. Rapport de stage MIM 2. École normale supérieure de Lyon (1998).

[38] M.A. Miller, Mortality for sets of 2 × 2 matrices. Math. Mag. 67 (1994) 210-213. | MR 1573026

[39] F. Nicolas, (Generalized) Post correspondence problem and semi-Thue systems. Available at http://arxiv.org/abs/0802.0726 (2008).

[40] M.S. Paterson, Unsolvability in 3 × 3 matrices. Stud. Appl. Math. 49 (1970) 105-107. | MR 255400 | Zbl 0186.01103

[41] E.L. Post, A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52 (1946) 264-268. | MR 15343 | Zbl 0063.06329

[42] E.L. Post, Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12 (1947) 1-11. | MR 20527 | Zbl 1263.03030

[43] G. Richomme, Private Communication (2007).

[44] J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003). | Zbl 1178.68002

[45] P. Schultz, Mortality of 2 × 2 matrices. Am. Math. Mon. 84 (1977) 463-464. | MR 1538398 | Zbl 0381.15007

[46] A. Tarski, A decision method for elementary algebra and geometry, 2nd edition. University of California Press (1951). | MR 44472 | Zbl 0044.25102

Cité par Sources :