congruence::KnuthBendix

class KnuthBendix : public libsemigroups::CongruenceInterface

Defined in knuth-bendix.hpp.

On this page we describe the functionality relating to the Knuth-Bendix algorithm for computing congruences of semigroups and monoids.

This page contains details of the member functions of the class congruence::KnuthBendix.

Example

KnuthBendix kb;
kb.set_number_of_generators(2);
kb.add_pair({0, 0, 0}, {0});
kb.add_pair({0}, {1, 1});

kb.number_of_classes();                            // 5
kb.word_to_class_index({0, 0, 1});          // 4
kb.word_to_class_index({0, 0, 0, 0, 1});    // 4
kb.word_to_class_index({0, 1, 1, 0, 0, 1}); // 4
kb.word_to_class_index({0, 0, 0});          // 0
kb.word_to_class_index({1});                // 1
kb.word_to_class_index({0, 0, 0, 0});       // 2

Note

congruence::KnuthBendix can only be used to compute 2-sided congruences.

Constructors

KnuthBendix()

Default constructor.

KnuthBendix(KnuthBendix const&)

Copy constructor.

KnuthBendix(T const&)

Constructs from FroidurePin instance.

KnuthBendix(fpsemigroup::KnuthBendix const&)

Construct from fpsemigroup::KnuthBendix .

KnuthBendix(std::shared_ptr<FroidurePinBase>)

Construct from std::shared_ptr to FroidurePin instance.

Deleted constructors

KnuthBendix(KnuthBendix&&) = delete

Deleted.

operator=(KnuthBendix const&) = delete

Deleted.

operator=(KnuthBendix&&) = delete

Deleted.

Member functions

knuth_bendix() const

Returns the underlying fpsemigroup::KnuthBendix .

Member functions and types 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.

class_index_type

Type for indices of congruence class indices.

const_contains(word_type const&, word_type const&) const override

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

const_iterator

Type for a const_iterator to the generating pairs.

contains(word_type const&, word_type const&) override

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_class_iterator

Type for a const_iterator to non-trivial classes.

non_trivial_classes()

Returns a shared pointer to the non-trivial classes.

non_trivial_classes_type

Type for 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.