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.
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},
mrnumber = {2981675},
zbl = {1252.20050},
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 SP - 355 EP - 399 VL - 46 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2012010/ DO - 10.1051/ita/2012010 LA - en ID - ITA_2012__46_3_355_0 ER -
%0 Journal Article %A Cassaigne, Julien %A Nicolas, Francois %T On the decidability of semigroup freeness %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 355-399 %V 46 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2012010/ %R 10.1051/ita/2012010 %G en %F ITA_2012__46_3_355_0
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] , Pell's equation and two generator free Möbius groups. Bull. London Math. Soc. 25 (1993) 527-532. | MR | Zbl
[2] and , Reachability problems in quaternion matrix and rotation semigroups. Inform. Comput. 206 (2008) 1353-1361. | MR | Zbl
[3] , 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 | Zbl
[4] , and , Codes and Automata, in Encycl. Math. Appl. 129 (2009). | MR | Zbl
[5] and , Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst. 36 (2003) 231-245. | MR | Zbl
[6] and , When is a pair of matrices mortal? Inf. Proc. Lett. 63 (1997) 283-286. | MR
[7] and , The boundedness of all products of a pair of matrices is undecidable. Syst. Control Lett. 41 (2000) 135-140. | MR | Zbl
[8] , and , 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
[9] and , The mortality problem for matrices of low dimensions. Theor. Comput. Syst. 35 (2002) 433-448. | MR | Zbl
[10] and , Free semigroups of 2 × 2 matrices. Pacific J. Math. 77 (1978) 57-69. | MR | Zbl
[11] , and , On the undecidability of freeness of matrix semigroups. Int. J. Algebra Comput. 9 (1999) 295-305. | MR | Zbl
[12] and , Some decision problems on integer matrices. RAIRO - Theor. Inf. Appl. 39 (2005) 125-131. | Numdam | MR | Zbl
[13] , Some remarks on PCP(k) and related problems. Bull. Eur. Assoc. Theoret. Comput. Sci. 12 (1980) 54-61.
[14] , and , The (generalized) Post correspondence problem with lists consisting of two words is decidable. Theoret. Comput. Sci. 21 (1982) 119-144. | MR | Zbl
[15] , and , On the problem of freeness of multiplicative matrix semigroups. Theoret. Comput. Sci. 411 (2010) 1115-1120. | MR | Zbl
[16] , 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 | Zbl
[17] , Algorithms in Geometric Group Theory. Ph.D. thesis, Graduate division of the University of California at Berkeley (1999). | MR
[18] and , Beardon's diophantine equations and non-free Möbius groups. Bull. Lond. Math. Soc. 32 (2000) 305-310. | Zbl
[19] , Private Communication (2008).
[20] and , Mortality in matrix semigroups. Am. Math. Mon. 108 (2001) 649-653. | MR | Zbl
[21] , and , Binary (generalized) Post correspondence problem. Theoret. Comput. Sci. 276 (2002) 183-204. | MR | Zbl
[22] , and , Undecidability bounds for integer matrices using Claus instances. Int. J. Found. Comput. Sci. 18 (2007) 931-948. | MR | Zbl
[23] and , Morphisms, in Handbook of formal languages, edited by G. Rozenberg and A. Salomaa 1 (1997) 439-510. | MR | Zbl
[24] , and , Introduction to automata theory, languages, and computation, 2nd edition. Addison-Wesley (2001). | MR | Zbl
[25] and , Matrix analysis. Corrected reprint of the 1985 original. Cambridge University Press (1990). | MR | Zbl
[26] , Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoret. Comput. Sci. 5 (1977) 183-204. | MR | Zbl
[27] , Algebraic number fields, in Pure Appl. Math. 55 (1973). | MR | Zbl
[28] , and , On the rational subset problem for groups. J. Algebra 309 (2007) 622-639. | MR | Zbl
[29] and , Polynomial-time algorithm for the orbit problem. J. Assoc. Comput. Mach. 33 (1986) 808-821. | MR
[30] , and , On the undecidability of the freeness of integer matrix semigroups. Int. J. Algebra Comput. 1 (1991) 223-226. | MR | Zbl
[31] and , More on mortality. Am. Math. Mon. 97 (1990) 37-38. | Zbl
[32] , Combinatorics on words, 2nd edition. Cambridge Mathematical Library, Cambridge University Press (1997). | MR | Zbl
[33] , Algebraic combinatorics on words, in Encycl. Math. Appl. 90 (2002). | MR | Zbl
[34] and , Combinatorial group theory, in Ergebnisse der Mathematik und ihrer Grenzgebiete 89 (1977). | MR | Zbl
[35] and , On finite semigroups of matrices. Theoret. Comput. Sci. 5 (1977) 101-111. | MR | Zbl
[36] and , Decision problems for semi-Thue systems with a few rules. Theoret. Comput. Sci. 330 (2005) 145-169. | MR | Zbl
[37] , 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] , Mortality for sets of 2 × 2 matrices. Math. Mag. 67 (1994) 210-213. | MR
[39] F. Nicolas, (Generalized) Post correspondence problem and semi-Thue systems. Available at http://arxiv.org/abs/0802.0726 (2008).
[40] , Unsolvability in 3 × 3 matrices. Stud. Appl. Math. 49 (1970) 105-107. | MR | Zbl
[41] , A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52 (1946) 264-268. | MR | Zbl
[42] , Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12 (1947) 1-11. | MR | Zbl
[43] , Private Communication (2007).
[44] , Éléments de théorie des automates. Vuibert (2003). | Zbl
[45] , Mortality of 2 × 2 matrices. Am. Math. Mon. 84 (1977) 463-464. | MR | Zbl
[46] , A decision method for elementary algebra and geometry, 2nd edition. University of California Press (1951). | MR | Zbl
Cité par Sources :
