Decision problems for word-hyperbolic semigroups

DOI10.1016/J.JALGEBRA.2016.07.007MaRDI QIDQ306545zbMATHOpenAlexWikidataFDO

Authors Alan J. Cain, Markus Pfeiffer

Publication date 31 August 2016

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

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1944128 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• An Improved Context-Free Recognizer
• Automatic monoids and change of generators
• Automatic semigroups
• CANCELLATIVITY IS UNDECIDABLE FOR AUTOMATIC SEMIGROUPS
• Context-free rewriting systems and word-hyperbolic structures with uniqueness
• Fundamentals of Computation Theory
• Greibach normal form transformation revisited.
• Hyperbolic groups and completely simple semigroups.
• Notions of automaticity in semigroups.
• On the definition of word hyperbolic groups.
• Term Rewriting and All That
• The isomorphism problem for all hyperbolic groups.
• Uniform decision problems for automatic semigroups.
• Word hyperbolic semigroups

Cited in

(8)

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

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)