Radoszewski-Rytter

libsemigroups contains an implementation of the Radoszewski-Rytter Algorithm [51] for testing equivalence of words in free bands.

The documentation for the functions in libsemigroups for free bands are linked to below.

Functions
template<typename T>
bool	freeband_equal_to (T first1, T last1, T first2, T last2)
	Check if two words represent the same element of a free band (iterators).
template<typename T>
bool	freeband_equal_to (T x, T y)
	Check if two words represent the same element of a free band (non-word_type).
bool	freeband_equal_to (word_type const &x, word_type const &y)
	Check if two words represent the same element of a free band.

Function Documentation

freeband_equal_to() [1/3]

template<typename T>

bool freeband_equal_to	(	T	first1,
		T	last1,
		T	first2,
		T	last2 )

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.

Returns

Return true if both words are the same as elements of the free band and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

The time complexity is \(O(mn)\) and space complexity is \(O(n)\) where \(n\) is the total length of x and y, and \(m\) is the number of distinct letters appearing in x and y.

freeband_equal_to() [2/3]

template<typename T>

bool freeband_equal_to	(	T	x,
		T	y )

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.

Returns

Return true if both words are the same as elements of the free band and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

The time complexity is \(O(mn)\) and space complexity is \(O(n)\) where \(n\) is the total length of x and y, and \(m\) is the number of distinct letters appearing in x and y.

freeband_equal_to() [3/3]

bool freeband_equal_to	(	word_type const &	x,
		word_type const &	y )

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.

Parameters

x	the first word to compare in the free band.
y	the second word to compare in the free band.

Returns

Return true if both words are the same as elements of the free band and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

The time complexity is \(O(mn)\) and space complexity is \(O(n)\) where \(n\) is the total length of x and y, and \(m\) is the number of distinct letters appearing in x and y.

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