Coverage for local/lib/python2.7/site-packages/sage/categories/examples/finite_semigroups.py : 100%

""" 

Examples of finite semigroups 

""" 

#***************************************************************************** 

# Copyright (C) 2008-2009 Nicolas M. Thiery <nthiery at users.sf.net> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# http://www.gnu.org/licenses/ 

#****************************************************************************** 

from sage.misc.cachefunc import cached_method 

from sage.sets.family import Family 

from sage.categories.semigroups import Semigroups 

from sage.structure.parent import Parent 

from sage.structure.unique_representation import UniqueRepresentation 

from sage.structure.element_wrapper import ElementWrapper 

class LeftRegularBand(UniqueRepresentation, Parent): 

r""" 

An example of a finite semigroup 

This class provides a minimal implementation of a finite semigroup. 

EXAMPLES:: 

sage: S = FiniteSemigroups().example(); S 

An example of a finite semigroup: the left regular band generated by ('a', 'b', 'c', 'd') 

This is the semigroup generated by:: 

sage: S.semigroup_generators() 

Family ('a', 'b', 'c', 'd') 

such that `x^2 = x` and `x y x = xy` for any `x` and `y` in `S`:: 

sage: S('dab') 

'dab' 

sage: S('dab') * S('acb') 

'dabc' 

It follows that the elements of `S` are strings without 

repetitions over the alphabet `a`, `b`, `c`, `d`:: 

sage: sorted(S.list()) 

['a', 'ab', 'abc', 'abcd', 'abd', 'abdc', 'ac', 'acb', 'acbd', 'acd', 

'acdb', 'ad', 'adb', 'adbc', 'adc', 'adcb', 'b', 'ba', 'bac', 

'bacd', 'bad', 'badc', 'bc', 'bca', 'bcad', 'bcd', 'bcda', 'bd', 

'bda', 'bdac', 'bdc', 'bdca', 'c', 'ca', 'cab', 'cabd', 'cad', 

'cadb', 'cb', 'cba', 'cbad', 'cbd', 'cbda', 'cd', 'cda', 'cdab', 

'cdb', 'cdba', 'd', 'da', 'dab', 'dabc', 'dac', 'dacb', 'db', 

'dba', 'dbac', 'dbc', 'dbca', 'dc', 'dca', 'dcab', 'dcb', 'dcba'] 

It also follows that there are finitely many of them:: 

sage: S.cardinality() 

64 

Indeed:: 

sage: 4 * ( 1 + 3 * (1 + 2 * (1 + 1))) 

64 

As expected, all the elements of `S` are idempotents:: 

sage: all( x.is_idempotent() for x in S ) 

True 

Now, let us look at the structure of the semigroup:: 

sage: S = FiniteSemigroups().example(alphabet = ('a','b','c')) 

sage: S.cayley_graph(side="left", simple=True).plot() 

Graphics object consisting of 60 graphics primitives 

sage: S.j_transversal_of_idempotents() # random (arbitrary choice) 

['acb', 'ac', 'ab', 'bc', 'a', 'c', 'b'] 

We conclude by running systematic tests on this semigroup:: 

sage: TestSuite(S).run(verbose = True) 

running ._test_an_element() . . . pass 

running ._test_associativity() . . . pass 

running ._test_cardinality() . . . pass 

running ._test_category() . . . pass 

running ._test_elements() . . . 

Running the test suite of self.an_element() 

running ._test_category() . . . pass 

running ._test_eq() . . . pass 

running ._test_new() . . . pass 

running ._test_not_implemented_methods() . . . pass 

running ._test_pickling() . . . pass 

pass 

running ._test_elements_eq_reflexive() . . . pass 

running ._test_elements_eq_symmetric() . . . pass 

running ._test_elements_eq_transitive() . . . pass 

running ._test_elements_neq() . . . pass 

running ._test_enumerated_set_contains() . . . pass 

running ._test_enumerated_set_iter_cardinality() . . . pass 

running ._test_enumerated_set_iter_list() . . . pass 

running ._test_eq() . . . pass 

running ._test_new() . . . pass 

running ._test_not_implemented_methods() . . . pass 

running ._test_pickling() . . . pass 

running ._test_some_elements() . . . pass 

""" 

def __init__(self, alphabet=('a','b','c','d')): 

r""" 

A left regular band. 

EXAMPLES:: 

sage: S = FiniteSemigroups().example(); S 

An example of a finite semigroup: the left regular band generated by ('a', 'b', 'c', 'd') 

sage: S = FiniteSemigroups().example(alphabet=('x','y')); S 

An example of a finite semigroup: the left regular band generated by ('x', 'y') 

sage: TestSuite(S).run() 

""" 

self.alphabet = alphabet 

Parent.__init__(self, category = Semigroups().Finite().FinitelyGenerated()) 

def _repr_(self): 

r""" 

TESTS:: 

sage: S = FiniteSemigroups().example() 

sage: S._repr_() 

"An example of a finite semigroup: the left regular band generated by ('a', 'b', 'c', 'd')" 

""" 

return "An example of a finite semigroup: the left regular band generated by %s"%(self.alphabet,) 

def product(self, x, y): 

r""" 

Returns the product of two elements of the semigroup. 

EXAMPLES:: 

sage: S = FiniteSemigroups().example() 

sage: S('a') * S('b') 

'ab' 

sage: S('a') * S('b') * S('a') 

'ab' 

sage: S('a') * S('a') 

'a' 

""" 

assert x in self 

assert y in self 

x = x.value 

y = y.value 

return self(x + ''.join(c for c in y if c not in x)) 

@cached_method 

def semigroup_generators(self): 

r""" 

Returns the generators of the semigroup. 

EXAMPLES:: 

sage: S = FiniteSemigroups().example(alphabet=('x','y')) 

sage: S.semigroup_generators() 

Family ('x', 'y') 

""" 

return Family([self(i) for i in self.alphabet]) 

def an_element(self): 

r""" 

Returns an element of the semigroup. 

EXAMPLES:: 

sage: S = FiniteSemigroups().example() 

sage: S.an_element() 

'cdab' 

sage: S = FiniteSemigroups().example(("b")) 

sage: S.an_element() 

'b' 

""" 

return self(''.join(self.alphabet[2:]+self.alphabet[0:2])) 

class Element (ElementWrapper): 

wrapped_class = str 

__lt__ = ElementWrapper._lt_by_value 

Example = LeftRegularBand