Action¶
-
using libsemigroups::SchreierSims::Action = typename TTraits::Action¶
Defined in
action.hpp
.This page contains details of the Action class in
libsemigroups
for finding actions of semigroups, or groups, on sets. The notion of an “action” in the context oflibsemigroups
is analogous to the notion of an orbit of a group.You are unlikely to want to use this class directly directly, but rather via the more convenient aliases libsemigroups::RightAction and libsemigroups::LeftAction.
The
run
member function finds points that can be obtained by acting on the seeds ofthis
by the generators ofthis
until no further points can be found, or Runner::stopped returnstrue
. This is achieved by performing a breadth first search.- See
side, ActionTraits, LeftAction, and RightAction.
- Example
using namespace libsemigroups; using PPerm = PPermHelper<16>::type; RightAction<PPerm, PPerm, ImageRightAction<PPerm, PPerm>> o; o.add_seed(PPerm::identity(16)); o.add_generator( PPerm({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}, 16)); o.add_generator( PPerm({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {1, 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, 16)); o.add_generator(PPerm({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, 16)); o.add_generator(PPerm({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}, 16)); o.reserve(70000); o.size(); // 65536 o.digraph().nr_scc(); // 17
- 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.
- Template Parameters
TElementType – the type of the elements of the semigroup.
TPointType – the type of the points acted on.
TActionType – the type of the action of elements of type
TElementType
on points of typeTPointType
. This type should be a stateless trivially default constructible class with a call operator of signaturevoid(TPointType&, TPointType const&, TElementType const&)
which computes the action of the 3rd argument on the 2nd argument, and stores it in the 1st argument. See, for example, libsemigroups::ImageLeftAction and libsemigroups::ImageRightAction.TTraits – the type of a traits class with the requirements of libsemigroups::ActionTraits.
TLeftOrRight – the libsemigroups::side of the action (i.e. if it is is a left or a right action).