The Action class

Class for determining the action of a semigroup or monoid on a set.

This page contains details of the Action class in libsemigroups_pybind11 for finding actions of semigroups, monoids, or groups, on sets. The notion of an “action” in the context of libsemigroups_pybind11 is analogous to the notion of an orbit of a group.

You are unlikely to want to use Action directly, but rather via the more convenient aliases RightAction and LeftAction.

The function Runner.run finds points that can be obtained by acting on the seeds of the action by the generators of the action until no further points can be found, or Runner.stopped returns True. This is achieved by performing a breadth first search.

In this documentation we refer to:

  • Element – the type of the elements of the underlying semigroup

  • Point – the type of the objects on which the semigroup elements act

  • Func – the function that computes the action of Element on Point

  • Side – the side of the action (if it is a left or a right action).

See also

LeftAction, RightAction, and Runner.

Important

The class Action has all the methods of the Runner class but, for boring technical reasons, is not a subclass of Runner. If thing is an instance of Action, then you can use thing as if it were an instance of Runner but isinstance(thing, Runner) will return False.

>>> from libsemigroups_pybind11 import RightAction, BMat8
>>> from libsemigroups_pybind11.bmat8 import row_space_basis
>>> o = RightAction(
...     seeds=[
...         row_space_basis(
...             BMat8([[1, 1, 1, 0], [1, 1, 0, 0], [0, 1, 0, 1], [0, 1, 0, 0]])
...         )
...     ],
...     generators=[
...         BMat8([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]),
...         BMat8([[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]),
...         BMat8([[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0]]),
...         BMat8([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [1, 0, 0, 1]]),
...         BMat8([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0]]),
...     ],
... )
>>> len(o)
553

Contents

Action

Class for determining the action of a semigroup or monoid on a set.

Action.add_generator(…)

Add a generator to the action.

Action.add_seed(…)

Add a seed to the action.

Action.apply(…)

This function returns the point obtained by applying the action defined by self to the point pt and the element x.

Action.cache_scc_multipliers(…)

Overloaded function.

Action.copy(…)

Copy an Action.

Action.current_size(…)

Returns the number of points found so far.

Action.empty(…)

Checks if the Action contains any points.

Action.generators(…)

Returns an iterator yielding the generators.

Action.init(…)

Re-initialize an existing object.

Action.multiplier_from_scc_root(…)

Returns a multiplier from a scc root to a given index.

Action.multiplier_to_scc_root(…)

Returns a multiplier from a given index to a scc root.

Action.number_of_generators(…)

Returns the number of generators.

Action.position(…)

Returns the position of a point in the so far discovered points.

Action.reserve(…)

Increase the capacity to a value that is greater or equal to val.

Action.root_of_scc(…)

Overloaded function.

Action.scc(…)

Returns a Gabow object for strongly connected components.

Action.size(…)

Returns the size of the fully enumerated action.

Action.word_graph(…)

Returns the word graph of the completely enumerated action.

Full API

class Action
__init__(self: Action, generators: list[Element] = None, seeds: list[Point] = None, func: collections.abc.Callable[[Point, Element], Point] = None, side: side = None) → None

Construct an action from generators, seeds, function, and side.

Keyword Arguments:

  • generators (list[Element])– at least one generator for the action.

  • seeds (list[Point]) – at least one seed point for the action.

  • func (collections.abc.Callable[[Point, Element], Point]) – the function defining the action.

  • side (side)– the side of the action.

Raises:

  • TypeError – if generators or seeds is not a list.

  • ValueError – if generators or seeds has length 0.

  • KeyError – if the action defined by the arguments is not implemented.

add_generator(self: Action, gen: Element) → Action

Add a generator to the action.

An Action instance represents the action of the semigroup generated by the elements added via this member function.

Parameters:

gen (Element) – the generator to add.

Returns:

self.

Return type:

Action

Complexity:

Constant.

add_seed(self: Action, seed: Point) → Action

Add a seed to the action.

A seed is just a starting point for the action, it will belong to the action, as will every point that can be obtained from the seed by acting with the generators of the action.

Parameters:

seed (Point) – the seed to add.

Returns:

self

Return type:

Action

Complexity:

Constant.

apply(self: Action, pt: Point, x: Element) → Point

This function returns the point obtained by applying the action defined by self to the point pt and the element x.

Parameters:

  • pt (Point) – the point.

  • x (Element) – the element.

Returns:

The image of pt under the action of x.

Return type:

Point

cache_scc_multipliers(*args, **kwargs)

Overloaded function.

cache_scc_multipliers(self: Action) → bool

Returns whether or not we are caching scc multipliers. If the returned value of this function is True, then the values returned by multiplier_from_scc_root() and multiplier_to_scc_root() are cached, and not recomputed every time one of these functions is called.

Returns:

True if caching is enabled, and False if not.

Return type:

bool

cache_scc_multipliers(self: Action, val: bool) → Action

Set whether or not to cache scc multipliers.

If the parameter val is True, then the values returned by multiplier_from_scc_root() and multiplier_to_scc_root() are cached, and not recomputed every time one of these functions is called.

Parameters:

val (bool) – the value.

Returns:

self.

Return type:

Action

Complexity:

Constant.

copy(self: Action) → Action

Copy an Action.

Returns:

A copy of the self.

Return type:

Action

current_size(self: Action) → int

Returns the number of points found so far.

Returns:

The current size.

Return type:

int

Complexity:

Constant.

empty(self: Action) → bool

Checks if the Action contains any points.

Returns:

True if the action contains no points (including seeds), and False if not.

Return type:

bool

Complexity:

Constant.

generators(self: Action) → collections.abc.Iterator[Element]

Returns an iterator yielding the generators.

Returns:

An iterator yielding the generators.

Return type:

collections.abc.Iterator[Element]

Complexity:

Constant.

init(self: Action) → Action

Re-initialize an existing object. This function puts an action object back into the same state as if it had been newly default constructed.

Returns:

self.

Return type:

Action

multiplier_from_scc_root(self: Action, pos: int) → Element

Returns a multiplier from a scc root to a given index.

Returns an element x of the semigroup generated by the generators in the action such that if r is the root of the strongly connected component containing self[pos], then after calling Func(res, r, x) the point res equals self[pos].

Parameters:

pos (int) – a position in the action.

Returns:

The multiplier.

Return type:

Element

Raises:

LibsemigroupsError – if there are no generators yet added or the index pos is out of range.

Complexity:

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type Element and \(n\) is the size of the fully enumerated orbit.

multiplier_to_scc_root(self: Action, pos: int) → Element

Returns a multiplier from a given index to a scc root.

Returns an element x of the semigroup generated by the generators in the action such that after Func(res, at(pos), x) the point res is the root of the strongly connected component containing self[pos].

Parameters:

pos (int) – a position in the action.

Returns:

The multiplier.

Return type:

Element

Raises:

LibsemigroupsError – if there are no generators yet added or the index pos is out of range.

Complexity:

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type Element and \(n\) is the size of the fully enumerated orbit.

number_of_generators(self: Action) → int

Returns the number of generators.

Returns:

The number of generators.

Return type:

int

Complexity:

Constant.

position(self: Action, pt: Point) → int | Undefined

Returns the position of a point in the so far discovered points.

Parameters:

pt (Point) – the point whose position is sought.

Returns:

The index of pt in self or UNDEFINED.

Return type:

int | Undefined

Complexity:

Constant.

reserve(self: Action, val: int) → Action

Increase the capacity to a value that is greater or equal to val.

Parameters:

val (int) – new capacity of an action instance.

Returns:

self.

Return type:

Action

Raises:

MemoryError – if val is too large.

Complexity:

At most linear in the size() of the Action.

root_of_scc(*args, **kwargs)

Overloaded function.

root_of_scc(self: Action, x: Point) → Point

Returns the root point of a strongly connected component containing a Point.

Parameters:

x (Point) – the point whose root we want to find.

Returns:

The root point.

Return type:

Point

Raises:

LibsemigroupsError – if the point x does not belong to the action.

Complexity:

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type Element and \(n\) is the size of the fully enumerated orbit.

root_of_scc(self: Action, pos: int) → Point

Returns the root point of a strongly connected component.

Parameters:

pos (int) – the index of the point in the action whose root we want to find.

Returns:

The root point.

Return type:

Point

Raises:

LibsemigroupsError – if the index pos is out of range.

Complexity:

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type Element and \(n\) is the size of the fully enumerated orbit.

scc(self: Action) → Gabow

Returns a Gabow object for strongly connected components.

Returns:

A Gabow object.

Return type:

Gabow

Complexity:

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type Element and \(n\) is the size of the fully enumerated orbit.

size(self: Action) → int

Returns the size of the fully enumerated action.

Returns:

The size of the action, a value of type int.

Return type:

int

Complexity:

The time complexity is \(O(mn)\) where \(m\) is the total number of points in the orbit and \(n\) is the number of generators.

word_graph(self: Action) → WordGraph

Returns the word graph of the completely enumerated action.

Returns:

The word graph of the action.

Return type:

WordGraph

Complexity:

At most \(O(mn)\) where \(m\) is the complexity of multiplying elements of type Element and \(n\) is the size of the fully enumerated orbit.