Mathematics – Group Theory
Scientific paper
2009-10-26
Mathematics
Group Theory
16 pages
Scientific paper
We study the way in which the abstract structure of a small overlap monoid is reflected in, and may be algorithmically deduced from, a small overlap presentation. We show that every C(2) monoid admits an essentially canonical C(2) presentation; by counting canonical presentations we obtain asymptotic estimates for the number of non-isomorphic monoids admitting a-generator, k-relation presentations of a given length. We demonstrate an algorithm to transform an arbitrary presentation for a C(m) monoid (m at least 2) into a canonical C(m) presentation, and a solution to the isomorphism problem for C(2) presentations. We also find a simple combinatorial condition on a C(4) presentation which is necessary and sufficient for the monoid presented to be left cancellative. We apply this to obtain algorithms to decide if a given C(4) monoid is left cancellative, right cancellative or cancellative, and to show that cancellativity properties are asymptotically visible in the sense of generic-case complexity.
No associations
LandOfFree
Uniform decision problems and abstract properties of small overlap monoids 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 and abstract properties of small overlap monoids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniform decision problems and abstract properties of small overlap monoids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-562729