KnuthBendixCongruenceByPairs

class KnuthBendixCongruenceByPairs : public libsemigroups::CongruenceByPairsHelper<FroidurePin<detail::KBE, FroidurePinTraits<detail::KBE, fpsemigroup::KnuthBendix>>>

Defined in cong-pair.hpp.

On this page, we describe the functionality relating to the brute force enumeration of pairs of elements belonging to a congruence (of any type) that is implemented in the class KnuthBendixCongruenceByPairs. This class is derived from CongruenceByPairs and implements the same algorithm. The only difference is that KnuthBendixCongruenceByPairs runs the Knuth-Bendix algorithm (see fpsemigroup::KnuthBendix) to completion, and then runs the brute force enumeration of pairs on the semigroup represented by the output of fpsemigroup::KnuthBendix. If the semigroup represented by the output of fpsemigroup::KnuthBendix is infinite, but the number of pairs belonging to the congruence represented by a KnuthBendixCongruenceByPairs instance is finite, then KnuthBendixCongruenceByPairs will terminate eventually, where as CongruenceByPairs would not (since it would attempt to enumerate the infinite semigroup represented by the output of fpsemigroup::KnuthBendix first).

See

congruence_type, tril, and CongruenceByPairs.

Example

fpsemigroup::KnuthBendix kb;
kb.set_alphabet(3);
kb.add_rule({0, 1}, {1, 0});
kb.add_rule({0, 2}, {2, 0});
kb.add_rule({0, 0}, {0});
kb.add_rule({0, 2}, {0});
kb.add_rule({2, 0}, {0});
kb.add_rule({1, 2}, {2, 1});
kb.add_rule({1, 1, 1}, {1});
kb.add_rule({1, 2}, {1});
kb.add_rule({2, 1}, {1});

KnuthBendixCongruenceByPairs kbp(twosided, kb);
kbp.add_pair({0}, {1});

kbp.nr_non_trivial_classes();  // == 1
kbp.cbegin_ntc()->size();      // == 5

Member types

class_index_type

Type for indices of congruence class indices.

const_iterator

Type for a const_iterator to the generating pairs.

non_trivial_class_iterator

Type for a const_iterator to non-trivial classes.

non_trivial_classes_type

Type for non-trivial classes.

Constructors

KnuthBendixCongruenceByPairs(congruence_type,KnuthBendix const &) noexcept

Construct a KnuthBendixCongruenceByPairs over the fpsemigroup::KnuthBendix instance kb representing a left/right/2-sided congruence according to type.

KnuthBendixCongruenceByPairs(congruence_type,std::shared_ptr<KnuthBendix>) noexcept

Construct a KnuthBendixCongruenceByPairs over the fpsemigroup::KnuthBendix instance kb representing a left/right/2-sided congruence according to type.

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.

nr_classes()

Compute the number of classes in the congruence.

nr_generating_pairs() const noexcept

The number of generating pairs.

nr_generators() const noexcept

The number of generators.

nr_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_nr_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(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.

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.