Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875794 | Theoretical Computer Science | 2017 | 22 Pages |
Abstract
Let κ be the signature that naturally generalizes the usual signature on groups: it consists of the multiplication, and of the (Ïâ1)-power. Given a pseudovariety of groups H, we denote by DRH the pseudovariety all finite semigroups whose regular R-classes lie in H. We prove that the word problem for κ-terms is decidable over DRH provided it is decidable over H (in general, the word problem for κ-terms is said to be decidable over a pseudovariety V if it is decidable whether two κ-terms define the same element in every semigroup of V). Further, we present a canonical form for elements in the free κ-semigroup over DRH, based on the knowledge of a canonical form for elements in the free κ-semigroup over H. This extends work of Almeida and Zeitoun on the pseudovariety of all finite R-trivial semigroups.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Célia Borlido,