Decision problems for word-hyperbolic semigroups

DOI10.1016/J.JALGEBRA.2016.07.007zbMATH Open1396.20063arXiv1303.1763OpenAlexW2964044258WikidataQ57990355 ScholiaQ57990355MaRDI QIDQ306545FDOQ306545

Authors: Alan J. Cain, Markus Pfeiffer 

Publication date: 31 August 2016

Published in: Journal of Algebra (Search for Journal in Brave)

Abstract: This paper studies decision problems for semigroups that are word-hyperbolic in the sense of Duncan & 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. 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 semigroup 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.

Full work available at URL: https://arxiv.org/abs/1303.1763

Recommendations

• Word hyperbolic semigroups
• Uniform decision problems for automatic semigroups.
• Hyperbolic groups and completely simple semigroups.
• scientific article
• Notions of hyperbolicity in monoids.

zbMATH Keywords

context-free languagesisomorphism problemundecidabilitydecision problemsword-hyperbolic semigroups

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Hyperbolic groups and nonpositively curved groups (20F67) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Term Rewriting and All That
• Title not available (Why is that?)
• Title not available (Why is that?)
• Notions of automaticity in semigroups.
• On the definition of word hyperbolic groups.
• Automatic semigroups
• Greibach normal form transformation revisited.
• Uniform decision problems for automatic semigroups.
• CANCELLATIVITY IS UNDECIDABLE FOR AUTOMATIC SEMIGROUPS
• Hyperbolic groups and completely simple semigroups.
• An Improved Context-Free Recognizer
• Title not available (Why is that?)
• Word hyperbolic semigroups
• CONTEXT-FREE REWRITING SYSTEMS AND WORD-HYPERBOLIC STRUCTURES WITH UNIQUENESS
• Automatic monoids and change of generators
• The isomorphism problem for all hyperbolic groups.
• Fundamentals of Computation Theory

Cited In (8)

• On the word problem for special monoids
• Word hyperbolic semigroups
• Title not available (Why is that?)
• A strong geometric hyperbolicity property for directed graphs and monoids.
• DECISION AND SEPARABILITY PROBLEMS FOR BAUMSLAG–SOLITAR SEMIGROUPS
• Hyperbolic groups and completely simple semigroups.
• MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS
• Uniform decision problems for automatic semigroups.

This page was built for publication: Decision problems for word-hyperbolic semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306545)