Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1192.20040
Cain, Alan J.; Oliver, Graham; Ruškuc, Nik; Thomas, Richard M.
Automatic presentations for semigroups. (English)
[J] Inf. Comput. 207, No. 11, 1156-1168 (2009). ISSN 0890-5401

A structure $\cal A=(A,R_1,\dots,R_n)$ consists of a set $A$, called the domain of $\cal A$, and there exists $r_i\ge 1$ such that $R_i$ is a subset of $A^{r_i}$ ($1\le i\le n$). A structure $\cal A$ has an automatic presentation over an alphabet, if it satisfies certain conditions (see Section 2). A structure that admits an automatic presentation is said to be FA-presentable. The paper under review is concerned with FA-presentable semigroups.\par First, the authors prove that all finitely generated commutative semigroups are FA-presentable (Theorem 6.1). Then they observe that any finitely generated subsemigroup of a semigroup admitting an automatic presentation has polynomial growth (Theorem 7.4). After that the authors consider one-relation semigroups and characterize one-relation semigroup presentations that define FA-presentable semigroups (Proposition 9.1). Later they give a complete classification of finitely generated FA-presentable cancellative semigroups and prove that a finitely generated cancellative semigroup is FA-presentable if and only if it embeds into a virtually Abelian group (Theorem 10.1).\par Finally, they consider the relationship between the class of FA-presentable semigroups and automatic semigroups (Proposition 11.2).
[Ahmet Sinan Çevik (Konya)]

MSC 2000:: *20M05 Free semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages

Keywords: finitely generated cancellative semigroups; finitely presented semigroups; automatic presentations; FA-presentable semigroups; commutative semigroups; automatic semigroups

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]