Abstract
We present efficient computational solutions to the problems of checking equality, performing multiplication, and computing minimal representatives of elements of free bands. A band is any semigroup satisfying the identity x^{2}≈x and the free band FB (k) is the free object in the variety of kgenerated bands. Radoszewski and Rytter developed a linear time algorithm for checking whether two words represent the same element of a free band. In this paper we describe an alternate linear time algorithm for the same problem. The algorithm we present utilises a representation of words as synchronous deterministic transducers that lend themselves to efficient (quadratic in the size of the alphabet) multiplication in the free band. This representation also provides a means of finding the shortlex least word representing a given free band element with quadratic complexity.
Original language  English 

Article number  113783 
Number of pages  28 
Journal  Theoretical Computer Science 
Volume  953 
Early online date  8 Mar 2023 
DOIs  
Publication status  Published  10 Apr 2023 
Keywords
 Free bands
 Word problem
 Complexity
 Transducers
 Minimal word representatives
 Algorithms
Fingerprint
Dive into the research topics of 'Polynomial time multiplication and normal forms in free bands'. Together they form a unique fingerprint.Datasets

reiniscirpons/freebandlib: v0.0.2 release
Cirpons, R. (Creator) & Mitchell, J. (Creator), Zenodo, 2022
Dataset