Decision problems for word-hyperbolic semigroups

DOI10.1016/j.jalgebra.2016.07.007zbMath1396.20063arXiv1303.1763OpenAlexW2964044258WikidataQ57990355 ScholiaQ57990355MaRDI QIDQ306545

Markus Pfeiffer, Alan J. Cain

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

undecidabilitydecision problemscontext-free languagesisomorphism problemword-hyperbolic semigroups

Mathematics Subject Classification ID

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

Related Items (3)

On the word problem for special monoids ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ A strong geometric hyperbolicity property for directed graphs and monoids.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The isomorphism problem for all hyperbolic groups.
• 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
• Term Rewriting and All That
• Word hyperbolic semigroups
• CONTEXT-FREE REWRITING SYSTEMS AND WORD-HYPERBOLIC STRUCTURES WITH UNIQUENESS
• Automatic monoids and change of generators
• Fundamentals of Computation Theory

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