Polynomial time multiplication and normal forms in free bands

Reinis Cirpons, James David Mitchell*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

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 x2≈x and the free band FB (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 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.
Original languageEnglish
Article number113783
Number of pages28
JournalTheoretical Computer Science
Volume953
Early online date8 Mar 2023
DOIs
Publication statusPublished - 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.

Cite this