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

r""" 

Finitely generated semigroups 

""" 

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

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

# 

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

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

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

import itertools 

from sage.misc.abstract_method import abstract_method 

from sage.misc.cachefunc import cached_method 

from sage.categories.category_with_axiom import CategoryWithAxiom 

from sage.categories.semigroups import Semigroups 

from sage.categories.enumerated_sets import EnumeratedSets 

class FinitelyGeneratedSemigroups(CategoryWithAxiom): 

r""" 

The category of finitely generated (multiplicative) semigroups. 

A :class:`finitely generated semigroup <Semigroups>` is a 

:class:`semigroup <Semigroups>` endowed with a distinguished 

finite set of generators (see 

:meth:`FinitelyGeneratedSemigroups.ParentMethods.semigroup_generators`). This 

makes it into an :class:`enumerated set <EnumeratedSets>`. 

EXAMPLES:: 

sage: C = Semigroups().FinitelyGenerated(); C 

Category of finitely generated semigroups 

sage: C.super_categories() 

[Category of semigroups, 

Category of finitely generated magmas, 

Category of enumerated sets] 

sage: sorted(C.axioms()) 

['Associative', 'Enumerated', 'FinitelyGeneratedAsMagma'] 

sage: C.example() 

An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd') 

TESTS:: 

sage: TestSuite(C).run() 

""" 

_base_category_class_and_axiom = (Semigroups, "FinitelyGeneratedAsMagma") 

@cached_method 

def extra_super_categories(self): 

r""" 

State that a finitely generated semigroup is endowed with a 

default enumeration. 

EXAMPLES:: 

sage: Semigroups().FinitelyGenerated().extra_super_categories() 

[Category of enumerated sets] 

""" 

return [EnumeratedSets()] 

def example(self): 

r""" 

EXAMPLES:: 

sage: Semigroups().FinitelyGenerated().example() 

An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd') 

""" 

return Semigroups().example("free") 

class ParentMethods: 

@abstract_method 

def semigroup_generators(self): 

r""" 

Return distinguished semigroup generators for ``self``. 

OUTPUT: a finite family 

This method should be implemented by all semigroups in 

:class:`FinitelyGeneratedSemigroups`. 

EXAMPLES:: 

sage: S = FiniteSemigroups().example() 

sage: S.semigroup_generators() 

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

""" 

# TODO: update transitive ideal 

def succ_generators(self, side="twosided"): 

r""" 

Return the successor function of the ``side``-sided Cayley 

graph of ``self``. 

This is a function that maps an element of ``self`` to all 

the products of ``x`` by a generator of this semigroup, 

where the product is taken on the left, right, or both 

sides. 

INPUT: 

- ``side``: "left", "right", or "twosided" 

.. TODO:: Design choice: 

- find a better name for this method 

- should we return a set? a family? 

EXAMPLES:: 

sage: S = FiniteSemigroups().example() 

sage: S.succ_generators("left" )(S('ca')) 

('ac', 'bca', 'ca', 'dca') 

sage: S.succ_generators("right")(S('ca')) 

('ca', 'cab', 'ca', 'cad') 

sage: S.succ_generators("twosided" )(S('ca')) 

('ac', 'bca', 'ca', 'dca', 'ca', 'cab', 'ca', 'cad') 

""" 

left = (side == "left" or side == "twosided") 

right = (side == "right" or side == "twosided") 

generators = self.semigroup_generators() 

return lambda x: (tuple(g * x for g in generators) if left else ()) + (tuple(x * g for g in generators) if right else ()) 

def __iter__(self): 

r""" 

Return an iterator over the elements of ``self``. 

This brute force implementation recursively multiplies 

together the distinguished semigroup generators. 

.. SEEALSO:: :meth:`semigroup_generators` 

EXAMPLES:: 

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

sage: it = S.__iter__() 

sage: list(it) 

['x', 'y', 'yx', 'xy'] 

""" 

from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet 

return iter(RecursivelyEnumeratedSet(self.semigroup_generators(), 

self.succ_generators(side="right"), 

enumeration='breadth')) 

def ideal(self, gens, side="twosided"): 

r""" 

Return the ``side``-sided ideal generated by ``gens``. 

This brute force implementation recursively multiplies the 

elements of ``gens`` by the distinguished generators of 

this semigroup. 

.. SEEALSO:: :meth:`semigroup_generators` 

INPUT: 

- ``gens`` -- a list (or iterable) of elements of ``self`` 

- ``side`` -- [default: "twosided"] "left", "right" or "twosided" 

EXAMPLES:: 

sage: S = FiniteSemigroups().example() 

sage: list(S.ideal([S('cab')], side="left")) 

['cab', 'acb', 'dcab', 'bca', 'abc', 'adcb', 'bdca', 

'cba', 'cdab', 'bac', 'dacb', 'dbca', 'adbc', 'bcda', 

'dbac', 'dabc', 'cbda', 'cdba', 'abdc', 'bdac', 'dcba', 

'cadb', 'badc', 'acdb', 'abcd', 'cbad', 'bacd', 'acbd', 

'bcad', 'cabd'] 

sage: list(S.ideal([S('cab')], side="right")) 

['cab', 'cabd'] 

sage: list(S.ideal([S('cab')], side="twosided")) 

['cab', 'acb', 'dcab', 'bca', 'cabd', 'abc', 'adcb', 

'acbd', 'bdca', 'bcad', 'cba', 'cdab', 'bac', 'dacb', 

'dbca', 'abcd', 'cbad', 'bacd', 'bcda', 'dbac', 'dabc', 

'cbda', 'cdba', 'abdc', 'adbc', 'bdac', 'dcba', 'cadb', 

'badc', 'acdb'] 

sage: list(S.ideal([S('cab')])) 

['cab', 'acb', 'dcab', 'bca', 'cabd', 'abc', 'adcb', 

'acbd', 'bdca', 'bcad', 'cba', 'cdab', 'bac', 'dacb', 

'dbca', 'abcd', 'cbad', 'bacd', 'bcda', 'dbac', 'dabc', 

'cbda', 'cdba', 'abdc', 'adbc', 'bdac', 'dcba', 'cadb', 

'badc', 'acdb'] 

""" 

from sage.sets.recursively_enumerated_set import RecursivelyEnumeratedSet 

return RecursivelyEnumeratedSet(gens, self.succ_generators(side=side)) 

class Finite(CategoryWithAxiom): 

class ParentMethods: 

def some_elements(self): 

r""" 

Return an iterable containing some elements of the semigroup. 

OUTPUT: the ten first elements of the semigroup, if they exist. 

EXAMPLES:: 

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

sage: S.some_elements() 

['x', 'y', 'yx', 'xy'] 

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

sage: S.some_elements() 

['x', 'y', 'z', 'xz', 'yx', 'yz', 'zx', 'zy', 'xy', 'yxz'] 

""" 

return list(itertools.islice(self, 10))