Radoszewski-Rytter

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

freeband_equal_to(x: list[int], y: list[int]) → bool

The free band is the free object in the variety of bands or idempotent semigroups. The free band \(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 \(FB(A)\) are the same as elements of the free band.

Parameters:

x (list[int]) – the first word to compare in the free band.
y (list[int]) – the second word to compare in the free band.

Returns:

True if both words are the same as elements of the free band and False otherwise.

Return type:

bool

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.

>>> from libsemigroups_pybind11 import freeband_equal_to
>>> 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