Polynomial time multiplication and normal forms in free bands

Reinis Cirpons; James David Mitchell

doi:10.1016/j.tcs.2023.113783

Polynomial time multiplication and normal forms in free bands

Reinis Cirpons, James David Mitchell^*

^*Corresponding author for this work

Pure Mathematics

Research output: Contribution to journal › Article › peer-review

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²≈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 language	English
Article number	113783
Number of pages	28
Journal	Theoretical Computer Science
Volume	953
Early online date	8 Mar 2023
DOIs	https://doi.org/10.1016/j.tcs.2023.113783
Publication status	Published - 10 Apr 2023

Keywords

Free bands
Word problem
Complexity
Transducers
Minimal word representatives
Algorithms

Access to Document

10.1016/j.tcs.2023.113783Licence: CC BY

Cirpons_2023_TCS_Polynomial-time_CC
Copyright © 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Final published version, 994 KBLicence: CC BY

Cite this

@article{84e528456b034336ad45b7ac41b2e754,

title = "Polynomial time multiplication and normal forms in free bands",

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.",

keywords = "Free bands, Word problem, Complexity, Transducers, Minimal word representatives, Algorithms",

author = "Reinis Cirpons and Mitchell, \{James David\}",

note = "Funding: Engineering and Physical Sciences Research Council (EP/V520123/1).",

year = "2023",

month = apr,

day = "10",

doi = "10.1016/j.tcs.2023.113783",

language = "English",

volume = "953",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Polynomial time multiplication and normal forms in free bands

AU - Cirpons, Reinis

AU - Mitchell, James David

N1 - Funding: Engineering and Physical Sciences Research Council (EP/V520123/1).

PY - 2023/4/10

Y1 - 2023/4/10

N2 - 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.

AB - 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.

KW - Free bands

KW - Word problem

KW - Complexity

KW - Transducers

KW - Minimal word representatives

KW - Algorithms

UR - https://www.scopus.com/pages/publications/85149436931

U2 - 10.1016/j.tcs.2023.113783

DO - 10.1016/j.tcs.2023.113783

M3 - Article

SN - 0304-3975

VL - 953

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 113783

ER -

Polynomial time multiplication and normal forms in free bands

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

reiniscirpons/freebandlib: v0.0.2 release

Cite this

Polynomial time multiplication and normal forms in free bands

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Datasets

reiniscirpons/freebandlib: v0.0.2 release

Cite this