On the decidability of semigroup freeness∗

Julien Cassaigne; Francois Nicolas

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 3, page 355-399
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Cassaigne, Julien, and Nicolas, Francois. "On the decidability of semigroup freeness∗." RAIRO - Theoretical Informatics and Applications 46.3 (2012): 355-399. <http://eudml.org/doc/277830>.

@article{Cassaigne2012,
abstract = {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.},
author = {Cassaigne, Julien, Nicolas, Francois},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Decidability; semigroup freeness; matrix semigroups; Post correspondence problem; decidability; free monoids; freeness problem; undecidability},
language = {eng},
month = {8},
number = {3},
pages = {355-399},
publisher = {EDP Sciences},
title = {On the decidability of semigroup freeness∗},
url = {http://eudml.org/doc/277830},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Cassaigne, Julien
AU - Nicolas, Francois
TI - On the decidability of semigroup freeness∗
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/8//
PB - EDP Sciences
VL - 46
IS - 3
SP - 355
EP - 399
AB - 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.
LA - eng
KW - Decidability; semigroup freeness; matrix semigroups; Post correspondence problem; decidability; free monoids; freeness problem; undecidability
UR - http://eudml.org/doc/277830
ER -

References

top
  1. A.F. Beardon, Pell’s equation and two generator free Möbius groups. Bull. London Math. Soc.25 (1993) 527–532.  Zbl0792.30031
  2. P. Bell and I. Potapov, Reachability problems in quaternion matrix and rotation semigroups. Inform. Comput.206 (2008) 1353–1361.  Zbl1151.03021
  3. M. Benois, Parties rationnelles du groupe libre. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, Série A269 (1969) 1188–1190.  Zbl0214.03903
  4. J. Berstel, D. Perrin and C. Reutenauer, Codes and Automata, in Encycl. Math. Appl.129 (2009).  
  5. V.D. Blondel and V. Canterini, Undecidable problems for probabilistic automata of fixed dimension. Theor. Comput. Syst.36 (2003) 231–245.  Zbl1039.68061
  6. V.D. Blondel and J.N. Tsitsiklis, When is a pair of matrices mortal?Inf. Proc. Lett.63 (1997) 283–286.  Zbl1337.68123
  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.  Zbl0985.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.  
  9. O. Bournez and M. Branicky, The mortality problem for matrices of low dimensions. Theor. Comput. Syst.35 (2002) 433–448.  Zbl1016.68038
  10. J.L. Brenner and A. Charnow, Free semigroups of 2 × 2 matrices. Pacific J. Math.77 (1978) 57–69.  Zbl0362.20035
  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.  Zbl1029.20027
  12. C. Choffrut and J. Karhumäki, Some decision problems on integer matrices. RAIRO – Theor. Inf. Appl.39 (2005) 125–131.  Zbl1081.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.  Zbl0493.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.  Zbl1193.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.  Zbl0549.68025
  17. Z. Grunschlag, Algorithms in Geometric Group Theory. Ph.D. thesis, Graduate division of the University of California at Berkeley (1999).  Zbl0953.20034
  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.  Zbl1024.11016
  19. L. Guyot, Private Communication (2008).  
  20. V. Halava and T. Harju, Mortality in matrix semigroups. Am. Math. Mon.108 (2001) 649–653.  Zbl0992.03052
  21. V. Halava, T. Harju and M. Hirvensalo, Binary (generalized) Post correspondence problem. Theoret. Comput. Sci.276 (2002) 183–204.  Zbl1023.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.  Zbl1202.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.  
  24. J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation, 2nd edition. Addison-Wesley (2001).  Zbl0980.68066
  25. R.A. Horn and C.R. Johnson, Matrix analysis. Corrected reprint of the 1985 original. Cambridge University Press (1990).  
  26. G. Jacob, Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoret. Comput. Sci.5 (1977) 183–204.  Zbl0388.15001
  27. G.J. Janusz, Algebraic number fields, in Pure Appl. Math.55 (1973).  
  28. M. Kambites, P.V. Silva and B. Steinberg, On the rational subset problem for groups. J. Algebra309 (2007) 622–639.  Zbl1123.20047
  29. R. Kannan and R.J. Lipton, Polynomial-time algorithm for the orbit problem. J. Assoc. Comput. Mach.33 (1986) 808–821.  Zbl1326.68162
  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.  Zbl0724.20036
  31. M. Krom and M. Krom, More on mortality. Am. Math. Mon.97 (1990) 37–38.  Zbl0702.15017
  32. M. Lothaire, Combinatorics on words, 2nd edition. Cambridge Mathematical Library, Cambridge University Press (1997).  Zbl0874.20040
  33. M. Lothaire, Algebraic combinatorics on words, in Encycl. Math. Appl.90 (2002).  Zbl1001.68093
  34. R.C. Lyndon and P.E. Schupp, Combinatorial group theory, in Ergebnisse der Mathematik und ihrer Grenzgebiete89 (1977).  Zbl0368.20023
  35. A. Mandel and I. Simon, On finite semigroups of matrices. Theoret. Comput. Sci.5 (1977) 101–111.  Zbl0368.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.  Zbl1078.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.  
  39. F. Nicolas, (Generalized) Post correspondence problem and semi-Thue systems. Available at (2008).  URIhttp://arxiv.org/abs/0802.0726
  40. M.S. Paterson, Unsolvability in 3 × 3 matrices. Stud. Appl. Math.49 (1970) 105–107.  Zbl0186.01103
  41. E.L. Post, A variant of a recursively unsolvable problem. Bull. Am. Math. Soc.52 (1946) 264–268.  Zbl0063.06329
  42. E.L. Post, Recursive unsolvability of a problem of Thue. J. Symbolic Logic12 (1947) 1–11.  Zbl1263.03030
  43. G. Richomme, Private Communication (2007).  
  44. J. Sakarovitch, Éléments de théorie des automates. Vuibert (2003).  
  45. P. Schultz, Mortality of 2 × 2 matrices. Am. Math. Mon.84 (1977) 463–464.  Zbl0381.15007
  46. A. Tarski, A decision method for elementary algebra and geometry, 2nd edition. University of California Press (1951).  Zbl0044.25102

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.