libsemigroups
Public Types | Public Member Functions | List of all members
libsemigroups::Congruence Class Reference

Class for congruence on a semigroup or fintely presented semigroup. More...

#include <cong.h>

Public Types

typedef size_t class_index_t
 Type for indices of congruence classes in a Congruence object. More...
 

Public Member Functions

 Congruence (std::string type, size_t nrgens, std::vector< relation_t > const &relations, std::vector< relation_t > const &extra)
 Constructor for congruences over a finitely presented semigroup. More...
 
 Congruence (std::string type, Semigroup *semigroup, std::vector< relation_t > const &genpairs)
 Constructor for congruences over a Semigroup object. More...
 
 ~Congruence ()
 A default destructor. More...
 
std::vector< relation_t > const & extra () const
 Returns the vector of extra relations (or equivalently, generating pairs) used to define the congruence. More...
 
void force_kbfp ()
 Use the Knuth-Bendix algorithm on a rewriting system RWS with rules obtained from Congruence::relations and Congruence::extra, followed by the Froidure-Pin algorithm on the resulting semigroup. More...
 
void force_kbp ()
 Use the Knuth-Bendix algorithm on a rewriting system RWS with rules obtained from Congruence::relations followed by an elementary orbit on pairs method on the resulting semigroup. More...
 
void force_p ()
 Use an elementary orbit algorithm which enumerates pairs of Element objects that are related in this. More...
 
void force_tc ()
 Use the Todd-Coxeter algorithm. More...
 
void force_tc_prefill ()
 Use the Todd-Coxeter algorithm after prefilling the table. More...
 
bool is_done () const
 Returns true if the structure of the congruence is known. More...
 
bool is_obviously_infinite ()
 This method tries to quickly determine whether or not the Congruence has infinitely many classes. More...
 
Partition< word_t > * nontrivial_classes ()
 Returns the non-trivial classes of the congruence. More...
 
size_t nr_classes ()
 Returns the number of congruences classes of this. More...
 
std::vector< relation_t > const & relations ()
 Returns the vector of relations used to define the semigroup over which the congruence is defined. More...
 
void set_max_threads (size_t nr_threads)
 Set the maximum number of threads for a Congruence over a Semigroup. More...
 
void set_pack (size_t val)
 Set the maximum number of active cosets in Todd-Coxeter before entering packing phase. More...
 
void set_prefill (RecVec< class_index_t > const &table)
 Specify a partial coset table for the Todd-Coxeter algorithm. More...
 
void set_relations (std::vector< relation_t > const &relations)
 Define the relations defining the semigroup over which this is defined. More...
 
void set_report (bool val) const
 Turn reporting on or off. More...
 
void set_report_interval (size_t val)
 Sets how often the core methods of Congruence report. More...
 
bool test_equals (word_t const &w1, word_t const &w2)
 Returns true if the words w1 and w2 belong to the same congruence class. More...
 
bool test_less_than (word_t const &w1, word_t const &w2)
 Returns true if the congruence class of w1 is less than that of w2. More...
 
class_index_t word_to_class_index (word_t const &word)
 Returns the index of the congruence class corresponding to word. More...
 

Detailed Description

Class for congruence on a semigroup or fintely presented semigroup.

This class represents a congruence on a semigroup defined either as an instance of a Semigroup object or as a finitely presented semigroup defined by generators and relations.

The structure of a Congruence is determined by running several different methods concurrently until one method returns an answer. The number of different threads used can be controlled, in part, by the value passed to Congruence::set_max_threads. The use of multiple threads to find the structure of a Congruence can cause the return values of certain methods to differ for different instances of mathematically equal objects.

This class and its implemented methods are somewhat rudimentary in the current version of libsemigroups.

Member Typedef Documentation

§ class_index_t

Type for indices of congruence classes in a Congruence object.

Constructor & Destructor Documentation

§ Congruence() [1/2]

libsemigroups::Congruence::Congruence ( std::string  type,
size_t  nrgens,
std::vector< relation_t > const &  relations,
std::vector< relation_t > const &  extra 
)

Constructor for congruences over a finitely presented semigroup.

The parameters are as follows:

  • type: a std::string describing the type of congruence, must be one of "left", "right", or "twosided".
  • nrgens: the number of generators.
  • relations: the defining relations of the semigroup over which the congruence being constructed is defined. Every relation_t in this parameter must consist of positive integers less than nrgens.
  • extra: additional relations corresponding to the generating pairs of the congruence being constructed. Every relation_t in this parameter must consist of positive integers less than nrgens.

This constructor returns an instance of a Congruence object whose type is described by the string type. The congruence is defined over the semigroup defined by nrgens generators and the relations relations and is the least congruence containing the generating pairs in extra.

For example, to compute a congruence over the free semigroup the parameter relations should be empty, and the relations defining the congruence to be constructed should be passed as the parameter extra. To compute a congruence over a finitely presented semigroup the relations defining the fintely presented semigroup must be passed as the parameter relations and the relations defining the congruence to be constructed should be passed as the parameter extra.

§ Congruence() [2/2]

libsemigroups::Congruence::Congruence ( std::string  type,
Semigroup semigroup,
std::vector< relation_t > const &  genpairs 
)

Constructor for congruences over a Semigroup object.

The parameters are as follows:

  • type: a std::string describing the type of congruence, must be one of "left", "right", or "twosided".
  • semigroup: a pointer to an instance of Semigroup. It is the responsibility of the caller to delete semigroup.
  • genpairs: additional relations corresponding to the generating pairs of the congruence being constructed. Every relation_t in this parameter must consist of positive integers less than the number of generators of semigroup (Semigroup::nrgens()).

This constructor returns an instance of a Congruence object whose type is described by the string type. The congruence is defined over the Semigroup semigroup and is the least congruence containing the generating pairs in extra.

§ ~Congruence()

libsemigroups::Congruence::~Congruence ( )
inline

A default destructor.

The caller is responsible for deleting the semigroup used to construct this, if any.

Member Function Documentation

§ extra()

std::vector<relation_t> const& libsemigroups::Congruence::extra ( ) const
inline

Returns the vector of extra relations (or equivalently, generating pairs) used to define the congruence.

§ force_kbfp()

void libsemigroups::Congruence::force_kbfp ( )

Use the Knuth-Bendix algorithm on a rewriting system RWS with rules obtained from Congruence::relations and Congruence::extra, followed by the Froidure-Pin algorithm on the resulting semigroup.

This method forces the use of the Knuth-Bendix algorithm to compute the congruence defined by the generators, Congruence::relations, and Congruence::extra of this followed by the Froidure-Pin algorithm on the resulting semigroup. The resulting semigroup consists of RWSE's and is enumerated using Semigroup::enumerate.

At present the Knuth-Bendix algorithm can only be applied to two-sided congruences, and this method asserts that this is a two-sided congruence.

Warning
Any existing data for the congruence is deleted by this method, and may have to be recomputed. The return values and runtimes of other methods applied to this may also be affected.
The Knuth-Bendix Algorithm may never terminate when applied to a finitely presented semigroup.

§ force_kbp()

void libsemigroups::Congruence::force_kbp ( )

Use the Knuth-Bendix algorithm on a rewriting system RWS with rules obtained from Congruence::relations followed by an elementary orbit on pairs method on the resulting semigroup.

This method forces the use of the Knuth-Bendix algorithm to compute the congruence defined by the generators and relations of this followed by an elementary orbit algorithm which enumerates pairs of Element objects of that semigroup which are related in this. Knuth-Bendix is applied to a rewriting system obtained from Congruence::relations.

This method only applies to a congruence over a finitely presented semigroups, and does not apply to a congruence defined using a concrete Semigroup object.

Note that this algorithm can be applied to left, right, and two-sided congruences (unlike KBFP).

Warning
Any existing data for the congruence is deleted by this method, and may have to be recomputed. The return values and runtimes of other methods applied to this may also be affected.
The Knuth-Bendix Algorithm may never terminate when applied to a finitely presented semigroup. Even if Knuth-Bendix completes the other algorithm that this method forces a Congruence to use will only terminate if there are finitely many pairs of elements related by this. The worst case space complexity of these algorithms is the square of the size of the semigroup over which this is defined.

§ force_p()

void libsemigroups::Congruence::force_p ( )

Use an elementary orbit algorithm which enumerates pairs of Element objects that are related in this.

The method forced by this is unlikely to terminate, or to be faster than the other methods, unless there are a relatively few pairs of elements related by the congruence.

This method only applies to a congruence created using a Semigroup object, and does not apply to finitely presented semigroups.

Warning
Any existing data for the congruence is deleted by this method, and may have to be recomputed. The return values and runtimes of other methods applied to this may also be affected.
The worst case space complexity of these algorithms is the square of the size of the semigroup over which this is defined.

§ force_tc()

void libsemigroups::Congruence::force_tc ( )

Use the Todd-Coxeter algorithm.

This methods forces the use of the Todd-Coxeter algorithm to compute the congruence. The implementation is based on one by Goetz Pfeiffer in GAP.

Warning
Any existing data for the congruence is deleted by this method, and may have to be recomputed. The return values and runtimes of other methods applied to this may also be affected.
The Todd-Coxeter Algorithm may never terminate when applied to a finitely presented semigroup.

§ force_tc_prefill()

void libsemigroups::Congruence::force_tc_prefill ( )

Use the Todd-Coxeter algorithm after prefilling the table.

This methods forces the use of the Todd-Coxeter algorithm to compute the congruence.

When applied to a congruence defined over a Semigroup, this method differs from Congruence::force_tc in that the so-called coset table used in the Todd-Coxeter algorithm is initialised to contain the right (or left) Cayley graph of the semigroup over which this is defined.

If this is not defined over a Semigroup (i.e. it is defined over a finitely presented semigroup), then this method does the same as force_tc.

Warning
Any existing data for the congruence is deleted by this method, and may have to be recomputed. The return values and runtimes of other methods applied to this may also be affected.
The Todd-Coxeter Algorithm may never terminate when applied to a finitely presented semigroup.

§ is_done()

bool libsemigroups::Congruence::is_done ( ) const
inline

Returns true if the structure of the congruence is known.

§ is_obviously_infinite()

bool libsemigroups::Congruence::is_obviously_infinite ( )

This method tries to quickly determine whether or not the Congruence has infinitely many classes.

If true is returned, then there are infinitely many classes in the congruence, but if false is returned, then the method could not determine whether or not there are infinitely many classes.

§ nontrivial_classes()

Partition< word_t > * libsemigroups::Congruence::nontrivial_classes ( )

Returns the non-trivial classes of the congruence.

The elements in these classes are represented as words in the generators of the semigroup over which the congruence is defined.

Warning
If this has infinitely many non-trivial congruence classes, then this method will only terminate when it can no longer allocate memory.

§ nr_classes()

size_t libsemigroups::Congruence::nr_classes ( )
inline

Returns the number of congruences classes of this.

This method is non-const because it may fully compute a data structure for the congruence.

Warning
The problem of determining the number of classes of a congruence over a finitely presented semigroup is undecidable in general, and this method may never terminate.

§ relations()

std::vector<relation_t> const& libsemigroups::Congruence::relations ( )
inline

Returns the vector of relations used to define the semigroup over which the congruence is defined.

This method is non-const since if the congruence is defined over a Semigroup object, then we may have to compute and store its relations.

§ set_max_threads()

void libsemigroups::Congruence::set_max_threads ( size_t  nr_threads)
inline

Set the maximum number of threads for a Congruence over a Semigroup.

This method sets the maximum number of threads to be used by any method of a Congruence object which is defined over a Semigroup. The number of threads is limited to the maximum of 1 and the minimum of nr_threads and the number of threads supported by the hardware.

If the congruence is not defined over a Semigroup, then the number of threads is not limited by this method.

§ set_pack()

void libsemigroups::Congruence::set_pack ( size_t  val)
inline

Set the maximum number of active cosets in Todd-Coxeter before entering packing phase.

This method only has any effect if used after Congruence::force_tc.

§ set_prefill()

void libsemigroups::Congruence::set_prefill ( RecVec< class_index_t > const &  table)
inline

Specify a partial coset table for the Todd-Coxeter algorithm.

The parameter table should be a partial coset table for use in the Todd-Coxeter algorithm:

  • table should have RecVec::nr_cols equal to the number of generators of the semigroup over which this is defined
  • every entry in table must be less than the number of rows in table.

For example, table can represent the right Cayley graph of a finite semigroup.

If this method is called after anything has been computed about the congruence, it has no effect.

§ set_relations()

void libsemigroups::Congruence::set_relations ( std::vector< relation_t > const &  relations)
inline

Define the relations defining the semigroup over which this is defined.

This method allows the relations of the semigroup over which the congruence is defined to be specified. This method asserts that the relations have not previously been specified.

§ set_report()

void libsemigroups::Congruence::set_report ( bool  val) const
inline

Turn reporting on or off.

If val is true, then some methods for a Congruence object may report information about the progress of the computation.

§ set_report_interval()

void libsemigroups::Congruence::set_report_interval ( size_t  val)
inline

Sets how often the core methods of Congruence report.

The smaller this value, the more often information will be reported.

§ test_equals()

bool libsemigroups::Congruence::test_equals ( word_t const &  w1,
word_t const &  w2 
)
inline

Returns true if the words w1 and w2 belong to the same congruence class.

The parameters w1 and w2 must be libsemigroups::word_t's consisting of indices of generators of the semigroup over which this is defined.

Warning
The problem of determining the return value of this method is undecidable in general, and this method may never terminate.

§ test_less_than()

bool libsemigroups::Congruence::test_less_than ( word_t const &  w1,
word_t const &  w2 
)
inline

Returns true if the congruence class of w1 is less than that of w2.

This method returns true if the congruence class of w1 is less than the class of w2 in a total ordering of congruence classes.

The parameters w1 and w2 should be libsemigroups::word_t's consisting of indices of the generators of the semigroup over which this is defined.

Warning
The method for finding the structure of a congruence is non-deterministic, and the total order of congruences classes may vary between different instances of the same congruence.
The problem of determining the return value of this method is undecidable in general, and this method may never terminate.

§ word_to_class_index()

class_index_t libsemigroups::Congruence::word_to_class_index ( word_t const &  word)
inline

Returns the index of the congruence class corresponding to word.

The parameter word must be a libsemigroups::word_t consisting of indices of the generators of the semigroup over which this is defined.

If this is defined over a semigroup with generators \(A\), then Congruence::word_to_class_index defines a surjective function from the set of all words over \(A\) to either \(\{0, 1, \ldots, n - 1\}\), where \(n\) is the number of classes, or to the non-negative integers \(\{0, 1, \ldots\}\) if this has infinitely many classes.

Warning
The method for finding the structure of a congruence is non-deterministic, and the return value of this method may vary between different instances of the same congruence.

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