Projects per year
Abstract
Automatic presentations, also called FA-presentations, were introduced to extend nite model theory to innite structures whilst retaining the solubility of interesting decision problems. A particular focus of research has been the classication of those structures of some species that admit automatic presentations. Whilst some successes have been obtained, this appears to be a dicult problem in general. A restricted problem, also of signicant interest, is to ask this question for unary automatic presentations: auto-matic 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 nite, but non-nitely generated unary FA-presentable semigroups may be innite. Every unary FA-presentable semigroup satises 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 classication is given of the unary FA-presentable completely simple 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 nite, but non-nitely generated unary FA-presentable semigroups may be innite. Every unary FA-presentable semigroup satises 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 classication is given of the unary FA-presentable completely simple semigroups.
Original language | English |
---|---|
Article number | 1250038 |
Number of pages | 29 |
Journal | International Journal of Algebra and Computation |
Volume | 22 |
Issue number | 4 |
DOIs | |
Publication status | Published - 8 Jun 2012 |
Keywords
- Automatic presentations
- Semigroups
- Regular languages
Fingerprint
Dive into the research topics of 'Unary FA-presentable semigroups'. Together they form a unique fingerprint.Projects
- 2 Finished
-
Automata Languages Decidability: Automata, Languages, Decidability in Algebra
Ruskuc, N. (PI) & Quick, M. (CoI)
1/03/10 → 31/05/14
Project: Standard
-
EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Ruskuc, N. (PI) & Quick, M. (CoI)
1/09/05 → 31/08/10
Project: Standard