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...
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...
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...
Download Results (CSV)