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

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.nr_active_rules();  // 31
kb.confluent();        // true

Public Types

const_normal_form_iterator

Type of an const iterator to a normal form.

froidure_pin_type

The type of the return value of froidure_pin() .

policy

This type contains various enums for specifying certain options to a KnuthBendix instance.

policy::overlap

Values for specifying how to measure the length of an overlap.

Constructors

KnuthBendix()

Default constructor.

KnuthBendix(FroidurePinBase&)

Constructs from a FroidurePin instance.

KnuthBendix(KnuthBendix const&)

Copy constructor.

KnuthBendix(std::shared_ptr<FroidurePinBase>)

Constructs from a shared pointer to a FroidurePin instance.

Member functions

active_rules() const

Returns a copy of the active rules.

cbegin_normal_forms(size_t const, size_t const)

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

cbegin_normal_forms(std::string const&, size_t const, size_t const)

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

cend_normal_forms()

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

confluent() const

Check confluence of the current rules.

contains_empty_string() const

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

gilman_digraph()

Returns the Gilman digraph.

knuth_bendix_by_overlap_length()

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

nr_active_rules() const noexcept

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

number_of_normal_forms(size_t const, size_t const)

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

operator<<(std::ostream &,KnuthBendix const &)

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

rewrite(std::string *) const

Rewrite a word in-place.

rewrite(std::string) const

Rewrite a word.

Settings

check_confluence_interval(size_t)

Set the interval at which confluence is checked.

max_overlap(size_t)

Set the maximum length of overlaps to be considered.

max_rules(size_t)

Set the maximum number of rules.

overlap_policy(policy::overlap)

Set the overlap policy.

Member functions and types inherited from FpSemigroupInterface

add_rule(relation_type)

Add a rule using a relation_type .

add_rule(rule_type)

Add a rule using a rule_type .

add_rule(std::initializer_list<size_t>, std::initializer_list<size_t>)

Add a rule using two word_type const references.

add_rule(std::string const&, std::string const&)

Add a rule using two std::string const references.

add_rule(word_type const&, word_type const&)

Add a rule using two word_type const references.

add_rules(FroidurePinBase&)

Add rules from a FroidurePin instance.

add_rules(std::vector<rule_type> const&)

Add rules in a vector.

alphabet() const noexcept

Returns a const reference to the alphabet.

alphabet(size_t) const

Returns the i th letter of the alphabet.

cbegin_rules() const noexcept

Returns an iterator pointing to the first rule.

cend_rules() const noexcept

Returns an iterator pointing one past the last rule.

char_to_uint(char) const

Convert a char to a letter_type .

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>)

Check if two words represent the same element.

equal_to(std::string const&, std::string const&) override

Check if two strings represent the same element.

equal_to(word_type const&, word_type const&)

Check if two words represent the same element.

froidure_pin()

Returns an isomorphic FroidurePin instance.

has_froidure_pin() const noexcept

Check if an isomorphic FroidurePin instance is known.

has_identity() const noexcept

Check if an identity has been set.

identity() const

Returns the identity (if any).

inverses() const

Returns the inverses (if any).

is_obviously_finite()

Check if the finitely presented semigroup is obviously finite.

is_obviously_infinite()

Check if the finitely presented semigroup is obviously infinite.

normal_form(std::initializer_list<letter_type>)

Returns a normal form for a word_type .

normal_form(std::string const&) override

Returns a normal form for a string.

normal_form(word_type const&)

Returns a normal form for a word_type .

nr_rules() const noexcept

Returns the number of rules.

rule_type

Type for rules.

set_alphabet(size_t)

Set the size of the alphabet.

set_alphabet(std::string const&)

Set the alphabet of the finitely presented semigroup.

set_identity(letter_type)

Set a character in alphabet() to be the identity using its index.

set_identity(std::string const&)

Set a character in alphabet() to be the identity.

set_inverses(std::string const&)

Set the inverses of letters in alphabet() .

size() override

Returns the size of the finitely presented semigroup.

string_to_word(std::string const&) const

Convert a string to a word_type .

string_type

Type for strings.

to_gap_string()

Returns a string containing GAP commands for defining a finitely presented semigroup.

uint_to_char(letter_type) const

Convert a letter_type to a char.

validate_letter(char) const

Validates a letter specified by a char.

validate_letter(letter_type) const

Validates a letter specified by an integer.

validate_word(std::string const&) const

Validates a word given by a std::string.

validate_word(word_type const&) const

Validates a word given by a word_type .

word_to_string(word_type const&) const

Convert a word_type to a std::string.

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.