Decision problems for word-hyperbolic semigroups

Cain, Alan J.; Pfeiffer, Markus

http://hdl.handle.net/10362/75297

Utilize este identificador para referenciar este registo.

Nome:	Descrição:	Tamanho:	Formato:
cp_wordhypdec.pdf		205.4 KB	Adobe PDF	Ver/Abrir

Contacte-nos

Autores

Cain, Alan J.

Pfeiffer, Markus

Resumo(s)

This paper studies decision problems for semigroups that are word-hyperbolic in the sense of Duncan and Gilman. A fundamental investigation reveals that the natural definition of a ‘word-hyperbolic structure’ has to be strengthened slightly in order to define a unique semigroup up to isomorphism. (This does not alter the class of word-hyperbolic semigroups.) The isomorphism problem is proven to be undecidable for word-hyperbolic semigroups (in contrast to the situation for word-hyperbolic groups). It is proved that it is undecidable whether a word-hyperbolic semigroup is automatic, asynchronously automatic, biautomatic, or asynchronously biautomatic. (These properties do not hold in general for word-hyperbolic semigroups.) It is proved that the uniform word problem for word-hyperbolic semigroups is solvable in polynomial time (improving on the previous exponential-time algorithm). Algorithms are presented for deciding whether a word-hyperbolic semigroup is a monoid, a group, a completely simple semigroup, a Clifford semigroup, or a free semigroup.

Descrição

project PEST-C/MAT/UI0144/2011 fellowship (IF/01622/2013/CP1161/CT0001). Part of the work described here was carried out during a visit by the first author to the University of St Andrews, which was funded by a London Mathematical Society Research in Pairs Grant (ref. 41410).