On the decidability of semigroup freeness
Julien Cassaigne, Francois Nicolas (2012)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset ⊆ , decide whether each element of has at most one factorization over . 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...