KnuthBendix class

Defined in knuth-bendix-class.hpp.

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

This class is used to represent a string rewriting system defining a 1- or 2-sided congruence on a finitely presented monoid or semigroup.

Template Parameters

Word	the type of the words in rules in the presentation.
Rewriter	the type of the rewriter.
ReductionOrder	the reduction ordering.

Example

Presentation<std::string> p;
p.contains_empty_word(true);
p.alphabet("abcd");
presentation::add_rule_no_checks(p, "ab", "");
presentation::add_rule_no_checks(p, "ba", "");
presentation::add_rule_no_checks(p, "cd", "");
presentation::add_rule_no_checks(p, "dc", "");
 
KnuthBendix kb(twosided, p);
 
!kb.confluent();              // true
kb.run();
kb.number_of_active_rules();  // 8
kb.confluent();               // true
kb.number_of_classes();       // POSITIVE_INFINITY

Warning

At present it is only possible to create KnuthBendix objects from presentations with alphabets containing at most:

• 128 letters if char a signed integer;
• 256 letters if char is an unsigned integer.

Topics
	Member types
	Public member types.
	Constructors + initializers
	Construct or re-initialize a KnuthBendix instance (public member function).
	Settings
	Settings that control the behaviour of a KnuthBendix instance.
	Common member functions
	Documentation of common member functions of Congruence, Kambites, KnuthBendix, and ToddCoxeter.
	Accessors
	Member functions that can be used to access the state of a KnuthBendix instance.

Functions
template<typename Word>
	KnuthBendix (congruence_kind, Presentation< Word > &&) -> KnuthBendix< Word >
	Deduction guide.
template<typename Word>
	KnuthBendix (congruence_kind, Presentation< Word > const &) -> KnuthBendix< Word >
	Deduction guide.
template<typename Word>
	KnuthBendix (KnuthBendix< Word > &&) -> KnuthBendix< Word >
	Deduction guide.
template<typename Word>
	KnuthBendix (KnuthBendix< Word > const &) -> KnuthBendix< Word >
	Deduction guide.

Function Documentation

KnuthBendix() [1/4]

template<typename Word>

KnuthBendix	(	congruence_kind	,
		Presentation< Word > &&	) -> KnuthBendix< Word >

Defined in knuth-bendix-class.hpp.

Deduction guide to construct a KnuthBendix<Word> from a

Presentation<Word> rvalue reference.

KnuthBendix() [2/4]

template<typename Word>

KnuthBendix	(	congruence_kind	,
		Presentation< Word > const &	) -> KnuthBendix< Word >

Defined in knuth-bendix-class.hpp.

Deduction guide to construct a KnuthBendix<Word> from a Presentation<Word> const reference.

KnuthBendix() [3/4]

template<typename Word>

KnuthBendix

(

KnuthBendix< Word > &&

)

-> KnuthBendix< Word >

Defined in knuth-bendix-class.hpp.

Deduction guide to construct a KnuthBendix<Word> from a KnuthBendix<Word> rvalue reference.

KnuthBendix() [4/4]

template<typename Word>

KnuthBendix

(

KnuthBendix< Word > const &

)

-> KnuthBendix< Word >

Defined in knuth-bendix-class.hpp.

Deduction guide to construct a KnuthBendix<Word> from a KnuthBendix<Word> const reference.