On the decidability of semigroup freeness

Details On the decidability of semigroup freeness On the decidability of semigroup freeness

2008-08-22

arxiv.org/abs/0808.3112v3

Computer Science

Discrete Mathematics

45 pages. 1 table

Scientific paper

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 of S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoid. 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 three-fold: (i) to present general results concerning 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.

Affiliated with

Also associated with

No associations

Rating

On the decidability of semigroup freeness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the decidability of semigroup freeness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the decidability of semigroup freeness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-185954