Automatic Presentations and Semigroup Constructions

作者：Cain Alan J^*; Oliver Graham; Ruskuc Nik; Thomas Richard M

来源：Theory of Computing Systems, 2010, 47(2): 568-592.

DOI：10.1007/s00224-009-9216-4

• Automatic presentation
• FA-presentable
• Semigroup construction
• Clifford semigroup
• Completely simple semigroup

An automatic presentation for a relational structure is, informally, an abstract representation of the elements of that structure by means of a regular language such that the relations can all be recognized by finite automata. A structure admitting an automatic presentation is said to be FA-presentable. This paper studies the interaction of automatic presentations and certain semigroup constructions, namely: direct products, free products, finite Rees index extensions and subsemigroups, strong semilattices of semigroups, Rees matrix semigroups, Bruck-Reilly extensions, zero-direct unions, semidirect products, wreath products, ideals, and quotient semigroups. For each case, the closure of the class of FA-presentable semigroups under that construction is considered, as is the question of whether the FA-presentability of the semigroup obtained from such a construction implies the FA-presentability of the original semigroup[s]. Classifications are also given of the FA-presentable finitely generated Clifford semigroups, completely simple semigroups, and completely 0-simple semigroups.

• 出版日期2010-8