Back to Search Start Over

The word problem for free adequate semigroups.

Authors :
Kambites, Mark
Kazda, Alexandr
Source :
International Journal of Algebra & Computation. Sep2014, Vol. 24 Issue 6, p893-907. 15p.
Publication Year :
2014

Abstract

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*SEMIGROUPS (Algebra)
*WORD problems (Mathematics)
*POLYNOMIALS
*CONSTRAINT satisfaction
*NORMAL forms (Mathematics)
*QUADRATIC forms

Details

Language :
English
ISSN :
02181967
Volume :
24
Issue :
6
Database :
Academic Search Index
Journal :
International Journal of Algebra & Computation
Publication Type :
Academic Journal
Accession number :
99451645
Full Text :
https://doi.org/10.1142/S0218196714500404
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details