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 thesecond
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
Warning
Copying iterators of this type is expensive. As a consequence, prefix incrementing
++it
the iteratorit
returned bycbegin_normal_forms
is significantly cheaper than postfix incrementingit++
.Warning
If the finitely presented semigroup represented by
this
is infinite thenmax
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
Warning
Copying iterators of this type is relatively expensive. As a consequence, prefix incrementing
++it
the iteratorit
returned bycbegin_normal_forms
is significantly cheaper than postfix incrementingit++
.Warning
If the finitely presented semigroup represented by
this
is infinite, thenmax
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.
See also
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 andfalse
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.
See also
number_of_normal_forms, cbegin_normal_forms, and cend_normal_forms.
- 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.