This article is cited in 6 papers

Finitely presented expansions of computably enumerable semigroups

D. R. Hirschfeldt^a, B. Khoussainov<sup>b

a</sup> Department of Mathematics, University of Chicago, Chicago, IL, USA
^b Department of Computer Science, University of Auckland, Auckland, New Zealand

Abstract: Every computable universal algebra has a finitely presented expansion. On the other hand, there are examples of finitely generated, computably enumerable universal algebras with no finitely presented expansions. It is natural to ask whether such examples can be found in well-known classes of algebras such as groups and semigroups. Here we build an example of a finitely generated, infinite, computably enumerable semigroup with no finitely presented expansions.We also discuss other interesting computability-theoretic properties of this semigroup.

Keywords: computably enumerable semigroup, finitely presented expansion.

UDC: 510.53+512.53

Received: 16.12.2011

 English version: Algebra and Logic, 2012, 51:5, 435–444

Bibliographic databases:

• 
• 
• 
•