Member functions

This page lists the member functions of the fpsemigroup::KnuthBendix class that are not present in its base classes.

std::vector<rule_type> libsemigroups::fpsemigroup::KnuthBendix::active_rules() const

Returns a copy of the active rules.

This member function returns a vector consisting of the pairs of strings which represent the rules of the KnuthBendix instance. The first entry in every such pair is greater than the second according to the reduction ordering of the KnuthBendix instance. The rules are sorted according to the reduction ordering used by the rewriting system, on the first entry.

Complexity

\(O(n)\) where \(n\) is the sum of the lengths of the words in rules of copy.

Parameters

(None)

Returns

A copy of the currently active rules, a value of type std::vector<rule_type>.

inline const_normal_form_iterator libsemigroups::fpsemigroup::KnuthBendix::cbegin_normal_forms(size_t min, size_t max)

Returns a forward iterator pointing at the first normal form with length in a given range.

If incremented, the iterator will point to the next least short-lex normal form (if it’s less than max in length). Iterators of the type returned by this function should only be compared with other iterators created from the same KnuthBendix instance.

See also

cend_normal_forms.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_normal_forms is significantly cheaper than postfix incrementing it++.

Warning

If the finitely presented semigroup represented by this is infinite then max should be chosen with some care.

Parameters
  • min – the minimum length of a normal form

  • max – one larger than the maximum length of a normal form.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type const_normal_form_iterator.

const_normal_form_iterator libsemigroups::fpsemigroup::KnuthBendix::cbegin_normal_forms(std::string const &lphbt, size_t min, size_t max)

Returns a forward iterator pointing at the first normal form with length in a given range.

If incremented, the iterator will point to the next least short-lex normal form (if it’s less than max in length). Iterators of the type returned by this function should only be compared with other iterators created from the same KnuthBendix instance.

See also

cend_normal_forms.

Warning

Copying iterators of this type is relatively expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_normal_forms is significantly cheaper than postfix incrementing it++.

Warning

If the finitely presented semigroup represented by this is infinite, then max should be chosen with some care.

Parameters
  • lphbt – the alphabet to use for the normal forms

  • min – the minimum length of a normal form

  • max – one larger than the maximum length of a normal form.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type const_normal_form_iterator.

inline const_normal_form_iterator libsemigroups::fpsemigroup::KnuthBendix::cend_normal_forms()

Returns a forward iterator pointing to one after the last normal form.

The iterator returned by this function can be compared with the return value of cbegin_normal_forms with any parameters.

Warning

The iterator returned by this function may still dereferenceable and incrementable, but will not point to a normal form in the correct range.

bool libsemigroups::fpsemigroup::KnuthBendix::confluent() const

Check confluence of the current rules.

Parameters

(None)

Returns

true if the KnuthBendix instance is confluent and false if it is not.

bool libsemigroups::fpsemigroup::KnuthBendix::contains_empty_string() const

Returns whether or not the empty string belongs in the system.

Complexity

\(O(n)\) where \(n\) is the number of rules.

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type bool.

ActionDigraph<size_t> const &libsemigroups::fpsemigroup::KnuthBendix::gilman_digraph()

Returns the Gilman digraph.

Parameters

(None)

Warning

This will terminate when the KnuthBendix instance is reduced and confluent, which might be never.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A const reference to a ActionDigraph.

void libsemigroups::fpsemigroup::KnuthBendix::knuth_bendix_by_overlap_length()

Run the Knuth-Bendix by considering all overlaps of a given length.

This function runs the Knuth-Bendix algorithm on the rewriting system represented by a KnuthBendix instance by considering all overlaps of a given length \(n\) (according to the options::overlap) before those overlaps of length \(n + 1\).

See also

run.

Complexity

See warning.

Parameters

(None)

Warning

This will terminate when the KnuthBendix instance is confluent, which might be never.

Returns

(None)

size_t libsemigroups::fpsemigroup::KnuthBendix::number_of_active_rules() const noexcept

Returns the current number of active rules in the KnuthBendix instance.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current number of active rules, a value of type size_t.

uint64_t libsemigroups::fpsemigroup::KnuthBendix::number_of_normal_forms(size_t min, size_t max)

Returns the number of normal forms with length in a given range.

Complexity

Assuming that this has been run until finished, the complexity of this function is at worst \(O(mn)\) where \(m\) is the number of letters in the alphabet, and \(n\) is the number of nodes in the gilman_digraph.

Parameters
  • min – the minimum length of a normal form to count

  • max – one larger than the maximum length of a normal form to count.

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

A value of type uint64_t.

friend std::ostream &libsemigroups::fpsemigroup::KnuthBendix::operator<<(std::ostream&, KnuthBendix const&)

This friend function allows a KnuthBendix object to be left shifted into a std::ostream, such as std::cout.

The currently active rules of the system are represented in the output.

std::string *libsemigroups::fpsemigroup::KnuthBendix::rewrite(std::string *w) const

Rewrite a word in-place.

The word w is rewritten in-place according to the current active rules in the KnuthBendix instance.

Parameters

w – the word to rewrite.

Returns

The argument w after it has been rewritten.

inline std::string libsemigroups::fpsemigroup::KnuthBendix::rewrite(std::string w) const

Rewrite a word.

Rewrites a copy of the word w rewritten according to the current rules in the KnuthBendix instance.

Parameters

w – the word to rewrite.

Returns

A copy of the argument w after it has been rewritten.