We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
UNARY FA-PRESENTABLE SEMIGROUPS.
- Authors
CAIN, ALAN J.; RUŠKUC, NIK; THOMAS, RICHARD M.; Howie, J.
- Abstract
Automatic presentations, also called FA-presentations, were introduced to extend finite model theory to infinite structures whilst retaining the solubility of interesting decision problems. A particular focus of research has been the classification of those structures of some species that admit automatic presentations. Whilst some successes have been obtained, this appears to be a difficult problem in general. A restricted problem, also of significant interest, is to ask this question for unary automatic presentations: automatic presentations over a one-letter alphabet. This paper studies unary FA-presentable semigroups. We prove the following: Every unary FA-presentable structure admits an injective unary automatic presentation where the language of representatives consists of every word over a one-letter alphabet. Unary FA-presentable semigroups are locally finite, but non-finitely generated unary FA-presentable semigroups may be infinite. Every unary FA-presentable semigroup satisfies some Burnside identity. We describe the Green's relations in unary FA-presentable semigroups. We investigate the relationship between the class of unary FA-presentable semigroups and various semigroup constructions. A classification is given of the unary FA-presentable completely simple semigroups.
- Subjects
GROUP theory; FINITE model theory; STATISTICAL decision making; MACHINE theory; UNARY algebras; PROBLEM solving
- Publication
International Journal of Algebra & Computation, 2012, Vol 22, Issue 4, p1250038
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S0218196712500385