Decision problems for word-hyperbolic semigroups

JOURNAL OF ALGEBRA

卷:465

Article

Cain, Man J.¹  Pfeiffer, Markus² 

[1] Univ Nova Lisboa, Fac Ciencias & Tecnol, Ctr Matemat & Aplicacoes, P-2829516 Caparica, Portugal

[2] Univ St Andrews, Sch Math & Stat, St Andrews KY16 9SX, Fife, Scotland

关键词: Word-hyperbolic semigroups;    Decision problems;    Undecidability;    Isomorphism problem;    Context-free languages;   

DOI  :  10.1016/j.jalgebra.2016.07.007

来源: Elsevier

【 摘 要 】

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. (C) 2016 Elsevier Inc. All rights reserved.

【 授权许可】

Free