Uniform decision problems in automatic semigroups

Details Uniform decision problems in automatic semigroups Uniform decision problems in automatic semigroups

2005-09-15

arxiv.org/abs/math/0509349v1

Mathematics

Rings and Algebras

19 pages

Scientific paper

We consider various decision problems for automatic semigroups, which involve the provision of an automatic structure as part of the problem instance. With mild restrictions on the automatic structure, which seem to be necessary to make the problem well-defined, the uniform word problem for semigroups described by automatic structures is decidable. Under the same conditions, we show that one can also decide whether the semigroup is completely simple or completely zero-simple; in the case that it is, one can compute a Rees matrix representation for the semigroup, in the form of a Rees matrix together with an automatic structure for its maximal subgroup. On the other hand, we show that it is undecidable in general whether a given element of a given automatic monoid has a right inverse.

Affiliated with

Also associated with

No associations

Rating

Uniform decision problems in automatic semigroups 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 Uniform decision problems in automatic semigroups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniform decision problems in automatic semigroups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-407451