CongruenceByPairs

template<typename TFroidurePinType>
class CongruenceByPairs : public libsemigroups::CongruenceInterface, protected libsemigroups::detail::BruidhinnTraits<TFroidurePinType::element_type>

Defined in cong-pair.hpp.

This class contains an implementation of a brute force breadth first search algorithm for computing left, right, and 2-sided congruences on semigroups and monoids.

This page contains a summary of the member functions of the class CongruenceByPairs, and related things in libsemigroups.

See also

congruence_kind and tril.

Example

using namespace libsemigroups;
auto      rg = ReportGuard();
using Transf = typename TransfHelper<8>::type;
FroidurePin<Transf> S({Transf({7, 3, 5, 3, 4, 2, 7, 7}),
                       Transf({1, 2, 4, 4, 7, 3, 0, 7}),
                       Transf({0, 6, 4, 2, 2, 6, 6, 4}),
                       Transf({3, 6, 3, 4, 0, 6, 0, 7})});

using P = CongruenceByPairs<decltype(S)>;

P cong1(right, S);
cong1.number_of_classes();   // 11804
P cong2(left, S);
cong2.number_of_classes();   // 11804
P cong3(twosided, S);
cong3.number_of_classes();   // 11804

Aliases

EqualTo

No doc.

Hash

No doc.

Product

No doc.

class_index_type

Type for indices of congruence class indices.

const_iterator

Type for a const_iterator to the generating pairs.

const_reference

The type of a const reference to an element_type.

element_type

The type of elements over which an instance of CongruenceByPairs is defined.

froidure_pin_type

No doc.

non_trivial_class_iterator

Type for a const_iterator to non-trivial classes.

non_trivial_classes_type

Type for non-trivial classes.

reference

The type of a reference to an element_type.

state_type

No doc.

Constructors

CongruenceByPairs(CongruenceByPairs const&) = default

A default copy constructor.

CongruenceByPairs(CongruenceByPairs&&) = default

A default move constructor.

CongruenceByPairs(congruence_kind, T const&)

Construct a CongruenceByPairs over the FroidurePin instance fp representing a left/right/2-sided congruence according to type.

CongruenceByPairs(congruence_kind, std::shared_ptr<FroidurePinBase>) noexcept

Construct a CongruenceByPairs over the FroidurePin instance S representing a left/right/2-sided congruence according to type.

CongruenceByPairs(congruence_kind, std::shared_ptr<T>, bool)

No doc.

Deleted constructors

CongruenceByPairs() = delete

A CongruenceByPairs instance is not default-constructible.

operator=(CongruenceByPairs const&) = delete

A CongruenceByPairs instance is not copy assignable.

operator=(CongruenceByPairs&&) = delete

A CongruenceByPairs instance is not move assignable.

Member functions inherited from CongruenceInterface

add_pair(std::initializer_list<size_t>, std::initializer_list<size_t>)

Add a generating pair to the congruence.

add_pair(word_type const&, word_type const&)

Add a generating pair to the congruence.

cbegin_generating_pairs() const noexcept

Returns a const iterator pointing to the first generating pair.

cbegin_ntc()

Returns a const iterator pointing to the first non-singleton class.

cend_generating_pairs() const noexcept

Returns a const iterator pointing one-after-the-end of the last generating pair.

cend_ntc()

Returns a const iterator pointing one-past-the-end of the last non-singleton class.

class_index_to_word(class_index_type)

Get a canonical representative of the i-th class.

const_contains(word_type const&, word_type const&) const

Check if a pair of words is known to belong to the congruence.

contains(word_type const&, word_type const&)

Check if a pair of words belongs to the congruence.

has_parent_fpsemigroup() const noexcept

Check if the congruence was constructed from a FpSemigroupInterface instance.

has_parent_froidure_pin() const noexcept

Check if the congruence was constructed from a FroidurePin instance.

has_quotient_froidure_pin() const noexcept

Check if the quotient semigroup has been computed.

is_quotient_obviously_finite()

Deterministically check if the quotient is finite.

is_quotient_obviously_infinite()

Deterministically check if the quotient is infinite.

kind() const noexcept

The handedness of the congruence (left, right, or 2-sided).

less(word_type const&, word_type const&)

Compare the indices of the classes containing two words.

non_trivial_classes()

Returns a shared pointer to the non-trivial classes.

number_of_classes()

Compute the number of classes in the congruence.

number_of_generating_pairs() const noexcept

The number of generating pairs.

number_of_generators() const noexcept

The number of generators.

number_of_non_trivial_classes()

The number of non-singleton classes.

parent_fpsemigroup() const

Get the parent FpSemigroupInterface instance (if any).

parent_froidure_pin() const

Get the parent FroidurePin instance (if any).

quotient_froidure_pin()

Returns a semigroup represented as an instance of a derived class of FroidurePinBase that is isomorphic to the quotient of the parent semigroup of this by the 2-sided congruence that this represents.

set_number_of_generators(size_t)

Set the number of generators of the congruence.

word_to_class_index(word_type const&)

Convert a word into the index of the class containing it.

Member functions inherited from Runner

dead() const noexcept

Check if the runner is dead.

finished() const

Check if run has been run to completion or not.

kill() noexcept

Stop run from running (thread-safe).

report() const

Check if it is time to report.

report_every() const noexcept

Get the minimum elapsed time between reports.

report_every(TIntType)

Set the minimum elapsed time between reports.

report_every(std::chrono::nanoseconds)

Set the minimum elapsed time between reports.

report_why_we_stopped() const

Report why run stopped.

run()

Run until finished .

run_for(TIntType)

Run for a specified amount of time.

run_for(std::chrono::nanoseconds)

Run for a specified amount of time.

run_until(T&&)

Run until a nullary predicate returns true or finished .

run_until(bool(*)())

Run until a nullary predicate returns true or finished .

running() const noexcept

Check if currently running.

running_for() const noexcept

Check if the runner is currently running for a particular length of time.

running_until() const noexcept

Check if the runner is currently running until a nullary predicate returns true.

started() const

Check if run has been called at least once before.

stopped() const

Check if the runner is stopped.

stopped_by_predicate() const

Check if the runner was, or should, stop because of the argument for run_until .

timed_out() const

Check if the amount of time passed to run_for has elapsed.