fpsemigroup::KnuthBendix¶

class KnuthBendix : public libsemigroups::FpSemigroupInterface ¶

Defined in knuth-bendix.hpp.

On this page we describe the functionality relating to the Knuth-Bendix algorithm for semigroups and monoids that is available in libsemigroups. This page contains a details of the member functions of the class fpsemigroup::KnuthBendix.

This class is used to represent a string rewriting system defining a finitely presented monoid or semigroup.

See also

congruence::KnuthBendix.

Example

KnuthBendix kb;
kb.set_alphabet("abc");

kb.add_rule("aaaa", "a");
kb.add_rule("bbbb", "b");
kb.add_rule("cccc", "c");
kb.add_rule("abab", "aaa");
kb.add_rule("bcbc", "bbb");

!kb.confluent();       // true
kb.run();
kb.number_of_active_rules();  // 31
kb.confluent();        // true

Public Types¶

`const_normal_form_iterator`	Type of an const iterator to a normal form.
`froidure_pin_type`
`options`
`options::overlap`

Constructors¶

`KnuthBendix()`
`KnuthBendix(FroidurePinBase&)`
`KnuthBendix(KnuthBendix const&)`
`KnuthBendix(KnuthBendix&&)`	Deleted.
`KnuthBendix(std::shared_ptr<FroidurePinBase>)`

Deleted constructors¶

`operator=(KnuthBendix &&) = delete`	Deleted.
`operator=(KnuthBendix const&) = delete`	Deleted.

Member functions¶

`active_rules() const`
`cbegin_normal_forms(size_t, size_t)`
`cbegin_normal_forms(std::string const&, size_t, size_t)`
`cend_normal_forms()`
`confluent() const`
`contains_empty_string() const`
`gilman_digraph()`
`knuth_bendix_by_overlap_length()`
`number_of_active_rules() const noexcept`
`number_of_normal_forms(size_t, size_t)`
`operator<<(std::ostream &,KnuthBendix const &)`
`rewrite(std::string *) const`
`rewrite(std::string) const`

Settings¶

`check_confluence_interval(size_t)`
`max_overlap(size_t)`
`max_rules(size_t)`
`overlap_policy(options::overlap)`

Member functions and types inherited from FpSemigroupInterface¶

`add_rule(relation_type)`
`add_rule(rule_type)`
`add_rule(std::initializer_list<size_t>, std::initializer_list<size_t>)`
`add_rule(std::string const&, std::string const&)`
`add_rule(word_type const&, word_type const&)`
`add_rules(FroidurePinBase&)`
`add_rules(std::vector<rule_type> const&)`
`alphabet() const noexcept`
`alphabet(size_t) const`
`cbegin_rules() const noexcept`
`cend_rules() const noexcept`
`char_to_uint(char) const`
`char_type`	Type for characters.
`const_iterator`	Type for const iterators to the defining rules.
`equal_to(std::initializer_list<letter_type>, std::initializer_list<letter_type>)`
`equal_to(std::string const&, std::string const&) override`
`equal_to(word_type const&, word_type const&)`
`froidure_pin()`
`has_froidure_pin() const noexcept`
`has_identity() const noexcept`
`identity() const`
`inverses() const`
`is_obviously_finite()`
`is_obviously_infinite()`
`normal_form(std::initializer_list<letter_type>)`
`normal_form(std::string const&) override`
`normal_form(word_type const&)`
`number_of_rules() const noexcept`
`rule_type`	Type for rules.
`set_alphabet(size_t)`
`set_alphabet(std::string const&)`
`set_identity(letter_type)`
`set_identity(std::string const&)`
`set_inverses(std::string const&)`
`size() override`
`string_to_word(std::string const&) const`
`string_type`	Type for strings.
`to_gap_string()`
`uint_to_char(letter_type) const`
`validate_letter(char) const`
`validate_letter(letter_type) const`
`validate_word(std::string const&) const`
`validate_word(word_type const&) const`
`word_to_string(word_type const&) const`