Ask Your Question
1

Introducing a finite monoid by giving its "multiplication" table

asked 2016-01-04 18:48:00 -0500

boumol gravatar image

I am interested in working with some finite monoids. Looking at http://doc.sagemath.org/html/en/refer... I have not found anything about how to define a finite monoid by simply providing its (binary) "multiplication" table.

Is there some way to do so?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2016-01-04 19:22:08 -0500

updated 2016-01-07 11:22:18 -0500

Hello,

Yes but not as direct as you may want. And the most important is: it really depends on what you want to do with these monoids.

If you put the following in a file like "finite_monoid.py"

from sage.structure.parent import Parent
from sage.categories.semigroups import Semigroups
from sage.structure.element_wrapper import ElementWrapper

class FiniteMonoidFromMultiplicationTable(Parent):
    def __init__(self, table):
        self._table = table
        Parent.__init__(self, category=Semigroups().Finite())

    def product(self, x, y):
        return self(self._table[x.value][y.value])

    def _repr_(self):
        return "Finite monoid on {} elements given by its multiplication table".format(len(self._table))

    def _element_constructor_(self, data):
        data = int(data)
        assert 0 <= data < len(self._table)
        return self.element_class(self, data)

    def __reduce__(self):
        return (FiniteMonoidFromMultiplicationTable,
                 (self._table,))

    def __eq__(self, other):
        return type(self) is type(other) and \
               self._table == other._table

    def __ne__(self, other):
        return not self == other

    class Element(ElementWrapper):
        wrapped_class = Integer

        def __reduce__(self):
            return self.parent(), (self.value,)

In the above code the most important are:

  • the constructor __init__ and the choice of the category Semigroups().Finite()

  • the method product that defines the product of elements from the multiplication table

  • the subclass Element and the method _element_constructor_ that tells how to construct elements

Then you can do from the console

sage: from finite_monoid import FiniteMonoidFromMultiplicationTable
sage: F = FiniteMonoidFromMultiplicationTable([[0, 0, 0], [0, 1, 1], [0, 1, 2]])
sage: e0 = F(0); e1 = F(1); e2 = F(2)
sage: print (e0, e1, e2)
sage: e0 * e1 * e2 * e1
0
sage: e1 * e2 * e2
1
sage: TestSuite(F).run()   # check thaat everything is fine

If you want to know more, you should have a look at the thematic tutorial How to implement new algebraic structures in Sage?.

EDIT:

Then you can do cartesian products and create morphisms as follows

sage: from sage.categories.morphism import SetMorphism
sage: from finite_monoid import FiniteMonoidFromMultiplicationTable
sage: F1 = FiniteMonoidFromMultiplicationTable([[0, 0, 0], [0, 1, 1], [0, 1, 2]])
sage: F2 = FiniteMonoidFromMultiplicationTable([[0, 1, 2], [1, 1, 2], [2, 2, 2]])
sage: F = cartesian_product([F1,F2])
sage: F((0,1)) * F((1,1))
(0, 1)
sage: TestSuite(F).run()

sage: from sage.categories.morphism import SetMorphism
sage: H = HomF1F2 = Hom(F1, F2, Semigroups())
sage: f = SetMorphism(H, lambda x: F2(2-x.value))
sage: e1_0 = F1(0)
sage: e1_1 = F1(1)
sage: e1_2 = F1(2)
sage: f(e1_1) * f(e1_2) == f(e1_1 * e1_2)
True
edit flag offensive delete link more

Comments

Thanks a lot. I will check whether this method allows using the issues already implemented for monoids (direct products, quotients, homomomorphisms, etc) without having to code anything else. Indeed, this reason was the motivation behind my question. By the way, do you already know the answer?

boumol gravatar imageboumol ( 2016-01-05 04:17:38 -0500 )edit
1

I updated the answer.

vdelecroix gravatar imagevdelecroix ( 2016-01-05 05:11:49 -0500 )edit
1

I guess there is a problem with one line of the current code "assert 0 <= data < len(self._table):". The last symbol of such line must be deleted.

boumol gravatar imageboumol ( 2016-01-07 10:38:15 -0500 )edit

you are definitely right! modified

vdelecroix gravatar imagevdelecroix ( 2016-01-07 11:22:06 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-01-04 18:48:00 -0500

Seen: 163 times

Last updated: Jan 07 '16