Voir la notice de l'article provenant de la source Numdam
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.
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :