Small overlap monoids II: automatic structures and normal forms

Details Small overlap monoids II: automatic structures and normal forms Small overlap monoids II: automatic structures and normal forms

2008-06-24

arxiv.org/abs/0806.3891v2

Mathematics

Rings and Algebras

17 pages

Scientific paper

We show that any finite monoid or semigroup presentation satisfying the small overlap condition C(4) has word problem which is a deterministic rational relation. It follows that the set of lexicographically minimal words forms a regular language of normal forms, and that these normal forms can be computed in linear time. We also deduce that C(4) monoids and semigroups are rational (in the sense of Sakarovitch), asynchronous automatic, and word hyperbolic (in the sense of Duncan and Gilman). From this it follows that C(4) monoids satisfy analogues of Kleene's theorem, and admit decision algorithms for the rational subset and finitely generated submonoid membership problems. We also prove some automata-theoretic results which may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Small overlap monoids II: automatic structures and normal forms 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 Small overlap monoids II: automatic structures and normal forms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small overlap monoids II: automatic structures and normal forms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-97801