libsemigroups
|
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... | |
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.
typedef size_t libsemigroups::Congruence::class_index_t |
Type for indices of congruence classes in a Congruence object.
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
.
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
.
|
inline |
A default destructor.
The caller is responsible for deleting the semigroup used to construct this
, if any.
|
inline |
Returns the vector of extra relations (or equivalently, generating pairs) used to define the congruence.
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.
this
may also be affected.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).
this
may also be affected.this
. The worst case space complexity of these algorithms is the square of the size of the semigroup over which this
is defined. 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.
this
may also be affected.this
is defined. 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.
this
may also be affected.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.
this
may also be affected.
|
inline |
Returns true
if the structure of the congruence is known.
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.
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.
this
has infinitely many non-trivial congruence classes, then this method will only terminate when it can no longer allocate memory.
|
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.
|
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.
|
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.
|
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.
|
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 definedtable
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.
|
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.
|
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.
|
inline |
Sets how often the core methods of Congruence report.
The smaller this value, the more often information will be reported.
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.
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.
|
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.