Defined in sims.hpp.

This class provides a pruner for pruning the search tree when looking for right congruences representing faithful actions. A right congruence represents a faithful action if and only if it does not contain any non-trivial two-sided congruence. Equivalently, a word graph of a right congruence represents a faithful action if and only if there is no nontrivial pair of words \((u, v)\) such that every vertex of the word graph is compatible with \((u, v)\).

See also: pruners; add_pruner

Public Member Functions
	SimsRefinerFaithful ()
	Default constructor.

	SimsRefinerFaithful (std::vector< word_type > const &forbid)
	Construct from set of forbidden pairs.

std::vector< word_type > const &	forbid () const noexcept
	Get the forbidden pairs defining the refiner.

SimsRefinerFaithful &	init ()
	Reinitialize an existing SimsRefinerFaithful object.

SimsRefinerFaithful &	init (std::vector< word_type > const &forbid)
	Reinitialize an existing SimsRefinerFaithful object from a set of forbidden pairs.

bool	operator() (Sims1::word_graph_type const &wg)
	Check if a word graph can be extended to one defining a faithful congruence.

Constructor & Destructor Documentation

◆ SimsRefinerFaithful()

SimsRefinerFaithful ( std::vector< word_type > const & forbid )

inlineexplicit

Constructs a SimsRefinerFaithful pruner with respect to the set of forbidden relations in forbid.

If forbid contains no trivial pairs (i.e. pairs of words that are equal in the underlying semigroup or monoid), then all word graphs rejected by SimsRefinerFaithful are guaranteed to not be extendable to a word graph representing a faithful congruence. Otherwise, the pruner will incorrectly reject all word graphs.

If in addition forbid is a set of relations containing all minimal congruence generating pairs of a given semigroup or monoid, then SimsRefinerFaithful will also correctly determine if a complete word graph represents a faithful congruence. Otherwise, the complete word graphs accepted by SimsRefinerFaithful are not guaranteed to be faithful and must be checked by some other means.

Warning: This method does not verify if forbid contains trivial pairs or not.

Member Function Documentation

◆ forbid()

std::vector< word_type > const & forbid ( ) const

inlinenodiscardnoexcept

Returns a const reference to the current forbidden pairs.

This function returns the defining forbidden pairs of a SimsRefinerFaithful instance.

Returns: A const reference to std::vector<word_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ init() [1/2]

SimsRefinerFaithful & init ( )

inline

This function puts an object back into the same state as if it had been newly default constructed.

Returns: A reference to *this.

◆ init() [2/2]

SimsRefinerFaithful & init ( std::vector< word_type > const & forbid )

inline

This function puts an object back into the same state as if it had been newly constructed from set of forbidden pairs forbid.

Returns: A reference to *this.

Warning: This method does not verify if forbid contains trivial pairs or not.

◆ operator()()

bool operator() ( Sims1::word_graph_type const & wg )

Returns false if there is no way of adding edges and nodes to

wg: which will result in a word graph defining a faithful congruence. Otherwise returns true.

The documentation for this class was generated from the following file:

/Users/jdm/libsemigroups/include/libsemigroups/sims.hpp