Polynomial time multiplication and normal forms in free bands

DOI10.1016/J.TCS.2023.113783MaRDI QIDQ6410455arXivFDO

Authors R. Cirpons, J. D. Mitchell

Publication date 12 September 2022

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2023.113783

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DMcs.DScs.FLmath.GRmath.RA

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}approxx$ and the free band $operatornameFB(k)$ is the free object in the variety of $k$-generated 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 checking 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 short-lex least word representing a given free band element with quadratic complexity.

This page was built for publication: Polynomial time multiplication and normal forms in free bands

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6410455)