Solution of the word problem for semigroups without cycles

2020/07/20 by A. Sh. Malkhasyan, Malkhasyan, Ara
Computer Science · #semigroups and automata theory #Computability, Logic, AI Algorithms #Algorithms and Data Compression

paper · pdf · doi:10.48550/arxiv.2007.09875

Abstract

We prove that in an arbitrary semigroup without cycles, the problem of divisibility and, therefore, the word problem is solvable.

Related

• Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x²=x³
• Word problem languages for completely regular semigroups
• Inverse semigroups with rational word problem are finite
• Context-free word problem semigroups
• Concrete algorithms for word problem and subsemigroup problem for\n semigroups which are disjoint unions of finitely many copies of the free\n monogenic semigroup