Paper Info
Title
The κ-word problem over DRH.
Abstract
Abstract Profinite techniques are explored in order to prove decidability of a word problem over a family of pseudovarieties of semigroups, which is parameterized by pseudovarieties of groups. 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.
Year
Venue
Field
2017
Theor. Comput. Sci.
Discrete mathematics,Combinatorics,Parameterized complexity,Word problem (mathematics education),Decidability,Canonical form,Multiplication,Semigroup,Mathematics
DocType
Volume
Citations 
Journal
702
0
PageRank 
References 
Authors
0.34
7
1
Name
Order
Citations
PageRank
Célia Borlido100.68