Finitely generated semigroups

class sage.categories.finitely_generated_semigroups.FinitelyGeneratedSemigroups(base_category)

Bases: sage.categories.category_with_axiom.CategoryWithAxiom

The category of finitely generated (multiplicative) semigroups.

A finitely generated semigroup is a semigroup endowed with a distinguished finite set of generators (see FinitelyGeneratedSemigroups.ParentMethods.semigroup_generators()). This makes it into an enumerated set.

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', 'FinitelyGeneratedAsMagma']
sage: C.example()
An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd')

TESTS:

sage: TestSuite(C).run()
class Finite(base_category)

Bases: sage.categories.category_with_axiom.CategoryWithAxiom

TESTS:

sage: C = Sets.Finite(); C
Category of finite sets
sage: type(C)
<class 'sage.categories.finite_sets.FiniteSets_with_category'>
sage: type(C).__base__.__base__
<class 'sage.categories.category_with_axiom.CategoryWithAxiom_singleton'>

sage: TestSuite(C).run()
class ParentMethods
some_elements()

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']
class FinitelyGeneratedSemigroups.ParentMethods
ideal(gens, side='twosided')

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.

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']
semigroup_generators()

Return distinguished semigroup generators for self.

OUTPUT: a finite family

This method should be implemented by all semigroups in FinitelyGeneratedSemigroups.

EXAMPLES:

sage: S = FiniteSemigroups().example()
sage: S.semigroup_generators()
Family ('a', 'b', 'c', 'd')
succ_generators(side='twosided')

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')
FinitelyGeneratedSemigroups.example()

EXAMPLES:

sage: Semigroups().FinitelyGenerated().example()
An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd')
FinitelyGeneratedSemigroups.extra_super_categories()

State that a finitely generated semigroup is endowed with a default enumeration.

EXAMPLES:

sage: Semigroups().FinitelyGenerated().extra_super_categories()
[Category of enumerated sets]