Free Bands¶
libsemigroups
contains an implementation of the Radoszewski-Rytter
algorithm [RR10] for testing equivalence of words in free
bands.
The functions in libsemigroups
for free bands are described on this page.
-
bool libsemigroups::freeband_equal_to(word_type &&x, word_type &&y)¶
Check if two given words represent the same element in the free band.
The free band is the free object in the variety of bands or idempotent semigroups. The free band \(\textrm{FB}(A)\) generated by some set \(A\) is the largest semigroup all of whose elements \(x\) are idempotent, i.e. satisfy \(x^2=x\). This function efficiently compares whether two words in the generators of \(\textrm{FB}(A)\) are the same as elements of the free band.
- Complexity
The time complexity is \(O(mn)\) and space complexity is \(O(n)\) where \(n\) is the total length of
x
andy
, and \(m\) is the number of distinct letters appearing inx
andy
.- Example
using namespace libsemigroups; freeband_equal_to({0, 1, 2, 3, 2, 1, 0}, {0, 1, 2, 3, 2, 3, 2, 1, 0}); // true freeband_equal_to({1, 2, 3}, {0, 1, 2}); // false freeband_equal_to({1, 4, 2, 3, 10}, {1, 4, 1, 4, 2, 3, 10}) // true freeband_equal_to({0, 1, 2, 3, 4, 0, 1, 2, 3, 4}, {4, 3, 2, 1, 0, 4, 3, 2, 1, 0}); // false freeband_equal_to({0, 1, 2, 1, 0, 1, 2}, {0, 1, 2}); // true freeband_equal_to({0, 1, 2, 3, 0, 1}, {0, 1, 2, 3, 3, 2, 2, 1, 0, 2, 1, 0, 2, 3, 0, 2, 1, 3, 2, 1, 2, 3, 2, 1, 0, 2, 0, 1, 0, 2, 0, 3, 2, 0, 1, 2, 2, 3, 0, 1}); // true
- Parameters
x – the first word to compare in the free band.
y – the second word to compare in the free band.
- Throws
(None) – This function guarantees not to throw a LibsemigroupsException.
- Returns
Return
true
if both words are the same as elements of the free band andfalse
otherwise.
-
template<typename T>
bool libsemigroups::freeband_equal_to(T x, T y)¶ Check if two given words represent the same element in the free band.
- Complexity
The time complexity is \(O(mn)\) and space complexity is \(O(n)\) where \(n\) is the total length of
x
andy
, and \(m\) is the number of distinct letters appearing inx
andy
.
- Template Parameters
T – any type that can be converted to
word_type
- Parameters
x – the first word to compare in the free band.
y – the second word to compare in the free band.
- Throws
(None) – This function guarantees not to throw a LibsemigroupsException.
- Returns
Return
true
if both words are the same as elements of the free band andfalse
otherwise.
-
template<typename T>
bool libsemigroups::freeband_equal_to(T first1, T last1, T first2, T last2)¶ Check if two given words represent the same element in the free band.
- Complexity
The time complexity is \(O(mn)\) and space complexity is \(O(n)\) where \(n\) is the total length of
x
andy
, and \(m\) is the number of distinct letters appearing inx
andy
.
- Template Parameters
T – any type that can be converted to
word_type
- Parameters
first1 – iterator to start of the first word.
last1 – iterator to end of the first word.
first2 – iterator to start of the second word.
last2 – iterator to end of the second word.
- Throws
(None) – This function guarantees not to throw a LibsemigroupsException.
- Returns
Return
true
if both words are the same as elements of the free band andfalse
otherwise.